[C国演义] 第十三章

三数之和

力扣链接

根据题目要求:

1. 返回的数对应的下标各不相同
2. 三个数之和等于0
3. 不可包含重复的三元组 – – 即顺序是不做要求的
   如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组
4. 输出答案顺序不做要求

暴力解法: 排序 + 3个for循环 + 去重 — — N^3, 肯定超时
优化: 排序 + 双指针 + 去重 — — N^2
优化的具体思路:
固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针)
去重有两种方法:
1.set去重
2 在循环内部缩小空间 — — 非常值得我们去尝试

1. set去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {

         // 排序
         sort(nums.begin(), nums.end());

        // 记录结果
        vector<vector<int>> res; 

         // 固定一个数 + 双指针
         int n = nums.size();
         for(int i = 0; i < n; i++) // 固定一个数
         {
             // 双指针优化
             int left = i+1, right = n-1;
             int targt = -nums[i];

             while(left < right)
             {
                 int sum = nums[left] + nums[right];
                 if(sum < targt)
                 {
                     left++;
                 }
                 else if(sum > targt)
                 {
                     right--;
                 }
                 else
                 {
                     res.push_back({nums[i], nums[left], nums[right]});
                     left++;
                     right--;
                 }
             }
         }

        // 去重
         set<vector<int>> result(res.begin(), res.end());
         res.clear();

         for(auto e : result)
         {
             res.push_back(e);
         }

         return res;
    }
};
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

上面的运行结果太慢了, 我们尝试一下 缩小空间去重👇👇👇

2. 缩小空间去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
         // 排序
         sort(nums.begin(), nums.end());

        // 记录结果
        vector<vector<int>> res; 

         // 固定一个数 + 双指针
         int n = nums.size();
         for(int i = 0; i < n;) // 固定一个数
         {
             // 双指针优化
             int left = i+1, right = n-1;
             int targt = -nums[i];

             while(left < right)
             {
                 int sum = nums[left] + nums[right];
                 if(sum < targt)
                 {
                     left++;
                 }
                 else if(sum > targt)
                 {
                     right--;
                 }
                 else
                 {
                     res.push_back({nums[i], nums[left], nums[right]});
                     left++;
                     right--;

                    // 去重left 和 right
                     while(left < right && nums[left] == nums[left-1])  left++;
                     while(right > left && nums[right] == nums[right+1])  right--;

                 }
             }
			
			// 去重i
             i++;
             while(i < n && nums[i] == nums[i-1])  i++;
         }

         return res;
    }
};
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

四数之和

力扣链接

这一题就跟上面的题目相似, 思路也很相似: 排序 + 固定两个数, 双指针优化 + 去重. 当然, 我们这里的去重逻辑也是 缩小空间去重

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;

        int n = nums.size();
        // 选定一个数, 内部用三数之和
        for(int i = 0; i < n;)
        {
            // 选定一个数, 内部使用双指针优化
            for(int j = i+1; j < n;)
            {
                int left = j+1, right = n-1;
                long int tar = target - (long int)(nums[i]+nums[j]);

                while(left < right)
                {
                    long int cur = nums[left] + nums[right];

                    if(cur < tar)  left++;
                    else if(cur > tar)  right--;
                    else
                    {
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++, right--;

                        // 去重left 和 right
                        while(left < right && nums[left] == nums[left-1])  left++;
                        while(right > left && nums[right] == nums[right+1])  right--;

                    }
                }

                // j的去重
                j++;
                while(j < n && nums[j] == nums[j-1])  j++;
            }

            // i的去重
            i++;
            while(i < n && nums[i] == nums[i-1])  i++;
        }

        return res;
    }
};
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

---

号令风霆迅，天声动北陬。
长驱渡河洛，直捣向燕幽。
马蹀阏氏血，旗袅可汗头。
归来报明主，恢复旧神州。 — — [宋] 岳飞 <送紫岩张先生北伐>