LeetCode 两数之和 & 三数之和& 四数之和

一、两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // val, index
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            if(mp.find(target - nums[i]) != mp.end()){
                return {i, mp[target - nums[i]]};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、四数相加 II

本题是使用哈希法的经典题目，而0015.三数之和 (opens new window)，0018.四数之和 (opens new window)并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，有很多细节需要处理

而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！

如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。

本题解题步骤：

• 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数
• 遍历A和B数组，统计两个数组元素之和，和出现的次数，放到map中
• 定义int变量count，用来统计 a+b+c+d = 0 出现的次数
• 在遍历C和D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // val, cnt
        unordered_map<int, int> mp;
        for(int a : nums1){
            for(int b : nums2){
                mp[a+b]++;
            }
        }
        int cnt = 0;
        for(int c : nums3){
            for(int d : nums4){
                if(mp.find(0 - c - d) != mp.end()){
                    cnt += mp[0 - c - d];
                }
            }
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、赎金信

说人话就是magazine必须要包含ransomNote中所有的字符，对于任意出现在ransomNote中的字符，magazine都能找到对应的，并且数量不能小于ransomNote中该字符出现的数量

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;
        for(char c : magazine){
            mp[c]++;
        }
        for(char c : ransomNote){
            mp[c]--;
            if(mp[c] < 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、三数之和

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end(), less<int>());
    vector<vector<int>> ans;
    for (int start = 0; start < nums.size() - 2; start++) {
        if (start > 0 && nums[start] == nums[start - 1]) {
            continue;
        }
        if (nums[start] > 0) {
            break;
        }
        int l = start + 1;
        int r = nums.size() - 1;
        while (l < r) {
            int sum = nums[start] + nums[l] + nums[r];
            if (sum == 0) {
                vector<int> tmp = { nums[start], nums[l], nums[r] };
                ans.push_back({ nums[start], 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 (sum > 0) {
                r--;
                while (l < r && nums[r] == nums[r + 1]) {
                    r--;
                }
            }
            else {
                l++;
                while (l < r && nums[l] == nums[l - 1]) {
                    l++;
                }
            }
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

五、最接近的三数之和

依然是固定最前面的指针，用另外两个指针寻找最接近的三数和，和三数之和一样去重即可

int threeSumClosest(vector<int>& nums, int target) {
    long ans = INT_MAX;
    sort(nums.begin(), nums.end(), less<int>());
    for(int i = 0; i < nums.size() - 2; i++){
        if(i > 0 && nums[i] == nums[i-1]){
            continue;
        }
        int l = i + 1;
        int r = nums.size() - 1;
        while(l < r){
            int sum = nums[i] + nums[l] + nums[r];
            ans = abs(ans-target) < abs(sum-target) ? ans : sum; 
            if(sum == target){
                break;
            }else if(sum < target){
                l++;
                while(l < r && nums[l] == nums[l-1]){
                    l++;
                }
            }else{
                r--;
                while(l < r && nums[r] == nums[r+1]){
                    r--;
                }
            }
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

六、四数之和

三数之和固定一个指针，用两个指针寻找三元组；四数之和固定两个指针，用两个指针寻找四元组

思路和三数之和完全一样，去重操作也一样，除了剪枝操作不一样

我们不能像三数之和一样，用第一个指针大于target就退出，因为后面指针指向的值可能是负数，四个指针之和依然有可能满足等于target的条件。为了避免后面的指针为负数，我们加一个前面指针不小于0的条件

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ans;

    if(nums.size() < 4){
        return ans;
    }
    sort(nums.begin(), nums.end(), less<int>());
    // 元素不少于4
    for(int i = 0; i <= nums.size() - 4; i++){
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 不能只用(nums[i] > target)作为退出条件，nums[i]比target大，也许数组后面还有负数，不能退出
        if (nums[i] > target && nums[i] >= 0) {
            break;
        }
        for(int j = i + 1; j <= nums.size() - 3; j++){
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                break;
            }

            int left = j + 1;
            int right = nums.size() - 1;
            while(left < right){
                long sum = long(nums[i]) + long(nums[j]) + long(nums[left]) + long(nums[right]);
                if(sum == target){
                    vector<int> tmp = {nums[i], nums[j], nums[left], nums[right]};
                    ans.push_back(tmp);
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }else if(sum < target){
                    left++;
                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                }else{
                    right--;
                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }
            }
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55