leetcode K sum 整理

本次题解包括

1. Two Sum
1. 3Sum
1. 3Sum Closest
1. 4Sum
1. 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:
1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
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++

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> vis;
		for (int i = 0; i < nums.size(); i++) {
			if (vis.find(target - nums[i]) != vis.end())
				return vector<int>{vis[target - nums[i]], i};
			vis[nums[i]] = i;
		}
		return vector<int>{-1, -1};
	}
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> vis = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (vis.containsKey(target - nums[i])) return new int[]{vis.get(target - nums[i]), i};
            vis.put(nums[i], i);
        }
        return new int[2];
    }
}

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        vis = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in vis:
                return [vis[diff], i]
            vis[num] = i

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.
1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目地址：leetcode 3Sum

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

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

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for(int i = 0; i < nums.size(); ++i){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int l = i + 1, r = nums.size() - 1; l < r;){
                int t = nums[i] + nums[l] + nums[r];
                if(t < 0) ++l;
                else if(t > 0) --r;
                else {
                    ans.push_back(vector<int>{nums[i], nums[l], nums[r]});
                    ++l;
                    while(l < r && nums[l] == nums[l - 1]) ++l;
                    --r;
                    while(l < r && nums[r] == nums[r + 1]) --r;
                }
            }
        }
        return ans;
    }
};

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int k = 0; k < nums.length - 1; k++) {
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            for (int i = k + 1, j = nums.length - 1; i < j; ) {
                if (nums[i] + nums[j] == -nums[k]) {
                    ans.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    i++;
                    j--;
                    while (i < j && nums[i] == nums[i - 1]) i++;
                    while (i < j && j != nums.length - 1 && nums[j] == nums[j + 1]) j--;
                } else if (nums[i] + nums[j] > -nums[k])
                    j--;
                else
                    i++;
            }
        }
        return ans;
    }
}

Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        nums.sort()
        ans = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            L, R = i + 1, n - 1
            while L < R:
                temp = nums[i] + nums[L] + nums[R]
                if temp == 0:
                    ans.append([nums[i], nums[L], nums[R]])
                    L += 1
                    R -= 1
                    while L < R and nums[L] == nums[L - 1]: L += 1
                    while R > L and nums[R] == nums[R + 1]: R -= 1
                elif temp > 0:
                    R -= 1
                else:
                    L += 1
        return ans

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.
1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目地址：leetcode 3Sum Closest

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

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

C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
int ans = target, diff = 0x7fffffff;
        for (int k = 0; k < nums.size(); k++) {
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            for(int i = k + 1, j = nums.size() - 1; i < j; ){
                int t = nums[k] + nums[i] + nums[j];
                if(abs(t - target) < diff){
                    ans = t;
                    diff = abs(t - target);
                }
                if(t == target){
                    j--;
                    i++;
                }else if(t > target)
                    j--;
                else
                    i++;
            }
        }
        return ans;
    }
};

Python

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        ans = ans_diff = 0x7fffffff
        n = len(nums)
        for i in range(n - 2):
            L, R = i + 1, n - 1
            while L < R:
                temp = nums[i] + nums[L] + nums[R]
                if temp == target:
                    return target
                elif temp > target:
                    R -= 1
                else:
                    L += 1

                diff = abs(temp - target)
                if diff < ans_diff:
                    ans, ans_diff = temp, diff
        return ans

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.
1
2
3
4
5
6
7
8
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题目地址：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++

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		int n = nums.size();
		for (int i = 0; i < n - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
			if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
			for (int j = i + 1; j < n - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;
				if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2]  > target) break;
				if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
				for (int L = j + 1, R = n - 1; L < R; ) {
					int t = nums[i] + nums[j] + nums[L] + nums[R];
					if (t == target) {
						ans.push_back(vector<int>{ nums[i], nums[j], nums[L], nums[R]});
						L++;
						R--;
						while (L < R && nums[L] == nums[L - 1]) L++;
						while (L < R && nums[R] == nums[R + 1]) R--;
					}
					else if (t > target) R--;
					else L++;
				}
			}
		}
		return ans;
	}
};

Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
                for (int L = j + 1, R = n - 1; L < R; ) {
                    int t = nums[i] + nums[j] + nums[L] + nums[R];
                    if (t == target) {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[L], nums[R])));
                        L++;
                        R--;
                        while (L < R && nums[L] == nums[L - 1]) L++;
                        while (L < R && nums[R] == nums[R + 1]) R--;
                    } else if (t > target) R--;
                    else L++;
                }
            }
        }
        return ans;
    }
}

Python

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(nums)
        nums.sort()
        ans = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]: continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target: break
            if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target: continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]: continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target: break
                if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target: continue
                L, R = j + 1, n - 1
                while L < R:
                    temp = nums[i] + nums[j] + nums[L] + nums[R]
                    if temp == target:
                        ans.append([nums[i], nums[j], nums[L], nums[R]])
                        L += 1
                        R -= 1
                        while L < R and nums[L] == nums[L - 1]: L += 1
                        while R > L and nums[R] == nums[R + 1]: R -= 1
                    elif temp > target:
                        R -= 1
                    else:
                        L += 1
        return ans

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++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0, j = nums.size() - 1; i < j;){
            if(nums[i] + nums[j] == target) return vector<int>{i + 1, j + 1};
            else if(nums[i] + nums[j] > target) j--;
            else i++;
        }
        return vector<int>{-1, -1};
    }
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0, j = nums.length - 1; i < j;){
            if(nums[i] + nums[j] == target) return new int[]{i + 1, j + 1};
            else if(nums[i] + nums[j] > target) j--;
            else i++;
        }
        return new int[]{-1, -1};
    }
}

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                return [i + 1, j + 1]
            elif nums[i] + nums[j] > target:
                j -= 1
            else:
                i += 1
        return [-1, -1]

这是leetcode Ksum题解整理

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