相向双指针题单

相向双指针

相向双指针实际上就是用$O(1)$的时间得到$O(n)$的信息,我们一般都是先暴力求解,然后再通过某些性质来获取更多的信息,比如有序,我们就可以减少枚举次数,来降低时间复杂度

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

思路:

这道题可以用相向双指针来实现,因为数组是有序的,所以我们假设两个数分别是$nums[i]$和$nums[j]$,如果两个数之和$>target$,我们就把右指针左移,否则就把左指针右移.我们可以这样理解,我们每次循环的时候,花费$O(1)$的时间得到了$O(n)$的信息,实际上就是把时间复杂度从暴力的$O(n^2)$降到了$O(n)$.

• 时间复杂度:$O(n)$

• 空间复杂度:$O(1)$

class Solution {
   
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
   
        int n = numbers.size();
        int left = 0, right = n - 1;
        while(left < right)
        {
   
            int s = numbers[left] + numbers[right];
            if(s > target)  right --;
            else if(s < target) left ++;
            else return {
   left + 1, right + 1};
        }
        return {
   left, right};
    }
};

15. 三数之和 - 力扣（LeetCode）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

思路:

我们也是一样的思路,我们要得到$nums[i]+nums[j]+nums[k]=0$,实际上我们枚举第一个数,然后让剩余两个数相加等于这个数的负数就变得和上一道题一样了,这道题还需要注意的一点是我们需要去重,就是我们相同的数只考虑最后一个,其他的就让他continue,这样就得到了结果

• 时间复杂度:$O(n^2)$

• 空间复杂度:$O(1)$

class Solution {
   
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
   
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());//先排序
        
        int n = nums.size();
        for(int i = 0; i < n - 2; i ++)
        {
   
            int x = nums[i];
            if(i && x == nums[i - 1])//去重
                continue;
            int j = i + 1, k = n - 1;
            while(j < k)
            {
   
                if(x + nums[j] + nums[k] > 0)
                    k --;
                else if(x + nums[j] + nums[k] < 0)
                    j ++;
                else
                {
   
                    res.push_back({
   x, nums[j], nums[k]});
                    j += 1;//这个尤其注意,每次输入进去一个答案,就j += 1
                    while(j < k && nums[j] == nums[j - 1])//也是去重
                        j ++;
                    k -= 1;
                    while(k > j && nums[k] == nums[k + 1])
                        k --;
                }
            }
        }
        return res;
    }
};

16. 最接近的三数之和 - 力扣（LeetCode）

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

思路:

这道题也是和上一题一样的思路,唯一的区别在于我们需要定义一个min_diff,然后每次和一个新的值进行比较

• 时间复杂度:$O(n^2)$

• 空间复杂度:$O(1)$

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = 0, n = nums.size();
        int min_diff = INT_MAX;
        for(int i = 0; i < n - 2; i ++)
        {
            int x = nums[i];
            if(i > 0 && x == nums[i - 1])
                continue;
            int j = i + 1, k = n - 1;
            while(j < k)
            {
                int s = x + nums[j] + nums[k];
                if(s == target)
                    return target;
                if(s > target)
                {
                    if(s - target < min_diff)
                    {
                        min_diff = s - target;
                        ans = s;
                    }
                    k --;
                }
                else
                {
                    if(target - s < mid_diff)
                    {
                        min_diff = target - s;
                        ans = s;
                    }
                    j ++;
                }
            }
        }
        return ans;
    }
};

18. 四数之和 - 力扣（LeetCode）

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

思路:

这道题也是沿用之前的思路,唯一不同的是由于有四个数,所以我们需要枚举二重循环来判别,还需要注意到是和可能会爆int,所以用longlong来存储

• 时间复杂度:$O(n^3)$

• 空间复杂度:$O(1)$

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 a = 0; a < n - 3; a ++)
        {
   
            long long x = nums[a];
            if(a > 0 && x == nums[a - 1])
                continue;
            for(int b = a + 1; b < n - 2; b ++)
            {
   
                long long y = nums[b];
                if(b > a + 1 && y == nums[b - 1])
                    continue;
                int c = b + 1, d = n - 1;
                while(c < d)
                {
   
                    long long s = x + y + nums[c] + nums[d];
                    if(s > target)  d --;
                    else if(s < target) c ++;
                    else
                    {
   
                        ans.push_back({
   (int) x, (int) y, nums[c], nums[d]});
                        c += 1;
                        while(c < d && nums[c] == nums[c - 1])
                            c += 1;
                        d -= 1;
                        while(c < d && nums[d] == nums[d + 1])
                            d -= 1;
                    }
                }
            }
        }
        return ans;
    }
};

2824. 统计和小于目标的下标对数目 - 力扣（LeetCode）

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

示例 1：

输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。

示例 2：

输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示：

• 1 <= nums.length == n <= 50
• -50 <= nums[i], target <= 50

思路:

还是双指针的思路,但是注意因为要统计答案如果 nums[left] + nums[right] < target，由于数组是有序的，nums[left] 与下标 iii 在 [left+1,right] 中的任何 nums[i] 相加，都是 < target 的，因此直接找到了 right - left 个合法数对，加到答案中，然后将 left 加一。

class Solution {
   
public:
    int countPairs(vector<int>& nums, int target) {
   
        sort(nums.begin(), nums.end());
        int ans = 0, left = 0, right = nums.size() - 1;
        while(left < right)
        {
   
            if(nums[left] + nums[right] < target)
            {
   
                ans += right - left;
                left ++;
            }
            else
            {
   
                right --;
            }
        }
        return ans;
    }
};

611. 有效三角形的个数 - 力扣（LeetCode）

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路:

这道题有几个注意点

• 根据示例一可以看出考虑重复的答案,所以不需要去重
• 由于要组成三角形,需要满足任意两边之和大于第三边,所以我们假设有$1<=a<=b<=c$,所以我们只需要求出$a+b>c$的个数即可,因为另外两个是一定满足的
• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$

class Solution {
   
public:
    int triangleNumber(vector<int>& nums) {
   
        sort(nums.begin(), nums.end());
        int ans = 0;
        for(int k = 2; k < nums.size(); k ++)
        {
   
            int c = nums[k];
            int i = 0, j = k - 1;
            while(i < j)
            {
   
                if(nums[i] + nums[j] > c)
                {
   
                    //如果nums[i] + nums[j] > c意味着i-j-1都可以满足条件一共有j-i个
                    ans += j - i;
                    j --;
                }
                else
                {
   
                    i ++;
                }
            }
        }
        return ans;
    }
};