leetcode K sum 整理

本次题解包括

  • 1. Two Sum
  • 15. 3Sum
  • 16. 3Sum Closest
  • 18. 4Sum
  • 167. Two Sum II – Input array is sorted

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

题目地址:leetcode Two Sum

题意:给定一个整形数组和目标和target,返回数组中,两个数的和等于目标和target的下标。(输入保证只有一个合法的解)

思路:最朴素的方法是,枚举第一个数,枚举第二个数,这样复杂度O(n^2)。 如何更好? 可以用二分,枚举第一个数x,然后第二个数为target – x,在数组中查找(需要先排序),复杂度O(nlogn), 。当然,如果把数组排好序,更好的方法是,直接双指针(接下来你会在3sum 4sum啥的看到类似的解法)。

说了这么多,其实最好的方法是直接hash。 把每个数作为key,下标作为值,放入hash表,然后遍历的时候找target – x。

C++

Java

Python

 

 


 

 

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

题目地址:leetcode 3Sum

题意:给定一个数组,求所有满足条件的三个数a,b,c,使得a+b+c=0  (结果要去重)

思路:排序。枚举第一个数,然后双指针,复杂度O(n^2) . 注意在过程中顺便去重。比如双指针中,找到满足条件的解了,L<R && nums[L] == nums[L-1],进行 L++

C++

Java

Python

 

 


 

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

题目地址:leetcode 3Sum Closest

题意:给定一个数组,求数组中的三个数a,b,c的和sum,  使得sum最接近于target

思路:和3sum差不多,先排序,然后双指针。

C++

Python

 

 


 

 

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

题目地址:leetcode 4Sum

题意:给定一个数组,求4个数,使得a+b+c+d=target( 结果要去重)

思路:和3sum差不多,都一个套路。先排序,然后枚举a和b,双指针代表c和d。  复杂度O(n^3)

可以用一些判断来加速,比如枚举第一个数的时候

  • nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target: break
    • 这是当前能凑齐的最小的4个数,比target后面都不用做了
  • nums[i] + nums[n – 3] + nums[n – 2] + nums[n – 1] < target: continue
    • 这是当前凑齐的最大的4个数,比target小,说明第一个数不够大

C++

Java

Python

 

 


 

 

167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目地址:leetcode Two Sum II – Input array is sorted

题目大意 :给定一个升序的数组,求两个数和为target,返回他们的下标

思路:双指针即可。。

C++

Java

Python

 

 

这是leetcode Ksum题解整理

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode K sum 整理
本文地址:https://www.hrwhisper.me/leetcode-2-sum-3-sum-4-sum-3-sum-closest-k-sum/

听说长得好看的已经打赏了

Leetcode , , . permalink.

4 thoughts on “leetcode K sum 整理

      • two sum 用 hash 当然更好啊:-D 当时第一次做的是用二分搜索的思路写的,好 tricky(捂脸):

        class Solution(object):
        def twoSum(self, nums, target):
        “””
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        “””
        s=sorted(nums)
        i,j=0,len(s)-1
        while(i<j):
        if(s[i]+s[j]target):
        j-=1
        else:
        break
        # deal for [3,3] 6
        if(s[i]==s[j]):
        k=nums.index(s[i])
        nums.remove(s[i])
        return [k,nums.index(s[j])+1]
        return [nums.index(s[i]),nums.index(s[j])]

Leave a Reply

Your email address will not be published. Required fields are marked *