# 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):

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.

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.

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.

• 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

C++

Java

Python

### 4 thoughts on “leetcode K sum 整理”

1. Kai says:

two sum 如果排序的话不就打乱了index的顺序？如何能先排序然后双指针最后还能返回索引？

• 对[0,1,3,2] => [[0,0],[1,1],[3,2],[2,3]] 的第一个元素排序，第二个为下标。 当然two sum用hash更好。

• 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])]