【算法】双指针(下)

查找总价格为目标值的两个商品

暴力解题

双指针解题

三数之和

双指针解题(左右指针)

四数之和

双指针解题

双指针关键点

注意事项

查找总价格为目标值的两个商品

题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

题目描述：

输⼊⼀个递增排序的数组和⼀个数字 s ，在数组中查找两个数，使得它们的和正好是 s 。如果有多

对数字的和等于 s ，则输出任意⼀对即可。

⽰例 1：

输⼊： nums = [2,7,11,15], target = 9

输出： [2,7] 或者 [7,2]

暴力解题

class Solution {
    public static int[] twoSum(int[] price, int target) {
        int n=price.length;
        int[] array=new int[2];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(price[i]+price[j]==target){
                    array[0]=price[i];
                    array[1]=price[j];
                    return array;
                }
            }
        }
        return array;
    }
}

双指针解题

解题思路：由于数组是升序的，我们可以使用【左右指针】，left和right指针分别指向最小值和最大值，判断其和是否等于目标值target。相等的话则直接返回，结束遍历

如果不相等，有两种情况：

·和小于target：采取增大最小值，逐渐接近target。即left++

·和大于target：采取减小最大值，逐渐接近target。即right--

解题代码：

class Solution {
    public static int[] twoSum(int[] price, int target) {
        int[] array=new int[2];
        int n=price.length;
        int left=0;
        int right=n-1;
        while(left<right){
            int sum=price[left]+price[right];
            if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }else{
                array[0]=price[left];
                array[1]=price[right];
                return array;
            }
        }
        return array;
    }
}

三数之和

题目链接：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

-10^5 <= nums[i] <= 10^5

双指针解题(左右指针)

题目分析：我们需要在数组中，找到满足 和为0且不重复 的三元组

重点：不重复

解题思路：既然是三元组，我们选择固定一个元素temp，然后只需找到【和为-temp的二元组】即可

1.排序，并且固定最大值(假设下标为i)：因为如果不排序，随机固定一个元素，无法使用双指针找到【和为-nums[i]的二元组】。

2.找到【和为-temp的二元组】:使用【左右指针】，left指针指向0，right指针指向 i 左侧的位置

如下图：

本题如何保证【不重复】呢？

·在找到一个【二元组】后，left和right指针需要【跳过重复】的元素：首先需要先跳过已找到的【二元组】，即left++，right--。其次，如果新的left、right处的元素与上一个【二元组】的数相同，也需要跳过。

·当使用完一次双指针算法后，固定的i也要【跳过重复】的元素：即当left和right指针相遇后，i--之后(for循环实现)，如果新的i处的元素与前一个i处的元素相等，需要额外的i--

假设最大值的下标为i，区间[left,right]是i位置左边的区间--也就是比i小的区间：

如果nums[left]+nums[right]>-nums[i]:这时需要减小【较大值】(right--)，尝试接近-nums[i]

如果nums[left]+nums[right]<-nums[i]:这时需要增大【较小值】(left++)，尝试接近-nums[i]

优化：在寻找三数之和为0时，当三个数中最大的那个数小于0时，三数之和只能小于0。

解题代码：

class Solution {
     public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> arr=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length-1;
        for(int i=n;i>=2;i--){
            if(nums[i]<0) break;
            int left=0;
            int right=i-1;
            while(left<right){
                int sum=nums[left]+nums[right];
                int target=-1*nums[i];
                if(sum>target){
                    right--;
                }else if(sum<target){
                    left++;
                }else{
                    arr.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1])right--;
                }
            }
            while(i>2&&nums[i]==nums[i-1])i--;
        }
        return arr;
    }
}

四数之和

题目链接：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

-10^9 <= nums[i] <= 10^9

-10^9 <= target <= 10^9

题目分析：我们需要在数组中，找到满足 和为target且不重复 的四元组

重点：不重复(解决方法与三数之和类似，这里不进行阐述)

双指针解题

解题思路：与三数之和类似。由于这里是【四元组】，我们选择固定两个元素。然后只需使用【左右指针】，找到一个【二元组】使其与固定的两个元素之和等于目标值(target)即可。

注意：由于 -10^9 <= nums[i] <= 10^9,当nums[i]+nums[j]+nums[left]+nums[right]时，这里可能会导致超出int类型的最大值，所以需要强制类型转换为(long)

解题代码：

class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> arr=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        //固定一个最小值和一个最大值
        for(int i=0;i<n;i++){
            //去重
            while(i<n&&i!=0&&nums[i]==nums[i-1]) i++;
            for(int j=n-1;j>i;j--){
                //去重
                while(j>i&&j!=n-1&&nums[j]==nums[j+1]) j--;
                int left=i+1;
                int right=j-1;
                while(left<right){
                    long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target){
                        arr.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                        //去重
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        while(left<right&&nums[right]==nums[right+1]) right--;
                    }else if(sum>target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return arr;
    }
}