【算法】双指针题解

冷不防 2022-10-05 00:41 197阅读 0赞

# 双指针 #

算法解释：（直接照搬齐姐的了）

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多

个数组的多个指针。

若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的

区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是

排好序的。

对于 C++ 语言，指针还可以玩出很多新的花样。一些常见的关于指针的操作如下。

## **指针与常量** ##

int x;
    int * p1 = &x; // 指针可以被修改，值也可以被修改
    const int * p2 = &x; // 指针可以被修改，值不可以被修改（const int）
    int * const p3 = &x; // 指针不可以被修改（* const），值可以被修改
    const int * const p4 = &x; // 指针不可以被修改，值也不可以被修改

只是介绍一下，这里的代码我还是用java来写

## 力扣167 两数之和 II - 输入有序数组 ##

**题目描述：**

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer\[0\] < answer\[1\] <= numbers.length 。

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

**示例 1：**

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

**示例 2：**

> 输入：numbers = \[2,3,4\], target = 6  
> 输出：\[1,3\]

**示例 3：**

> 输入：numbers = \[-1,0\], target = -1  
> 输出：\[1,2\]

提示：

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

### 1. 暴力破解法 ###

**解题思路：**

定义双层`for`循环，来进行遍历，如果有两数相加等于`target`，那么就将其返回。

**代码：**

class Solution {
        
        public int[] twoSum(int[] numbers, int target) {
        
     for (int i = 0; i < numbers.length; i++) {
        
                for (int j = 0; j < numbers.length; j++) {
        
                    //判断下标，是否重复，如果重复跳过
                    if (i==j){
        
                        continue;
                    }else {
        
                        if (numbers[i]+numbers[j]==target){
        
                            int [] arr=new int[2];
                            arr[0]=i+1;
                            arr[1]=j+1;
                            return arr;
                        }
                    }
                    
                }
            }
            return null;
        }
    }

执行用时：332 ms, 在所有 Java 提交中击败了5.02%的用户

内存消耗：38.2 MB, 在所有 Java 提交中击败了98.43%的用户

但很明显发现，执行效率是真的慢

### 2. 双指针 ###

**解题思路：**

我们在题干中发现，数组已经是排好序的，那么我们可以利用双指针来解决此问题。

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

**代码：**

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

执行用时：1 ms, 在所有 Java 提交中击败了93.80%的用户

内存消耗：38.4 MB, 在所有 Java 提交中击败了92.24%的用户

### 3. 二分查找（待写） ###

## 力扣 88 合并两个有序数组 ##

**题目描述：**

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

**示例 1：**

> 输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
> 输出：\[1,2,2,3,5,6\]

**示例 2：**

> 输入：nums1 = \[1\], m = 1, nums2 = \[\], n = 0  
> 输出：\[1\]

提示：

nums1.length == m + n  
nums2.length == n  
0 <= m, n <= 200  
1 <= m + n <= 200  
\-109 <= nums1\[i\], nums2\[i\] <= 109

### 1. 先插入，后排序 ###

**解题思路：**

将数组 num1、num2的数据全都放入num1，然后进行排序

**代码：**

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    	 for (int i = 0; i <n ; i++) {
        
                nums1[m+i]=nums2[i];
         	   }
            Arrays.sort(nums1);
        }
    }

执行用时: **1 ms**

内存消耗: **38.1 MB**

### 2. 双指针 ###

**解题思路：**

因为两个数组已经排好序，定义两个数组num1 、num2的头指针，定义一个长度为 `n+m` arr 的数组，每次从两个数组指针指向的数字中取最小值放入arr 中。

![gif1][]

**代码：**

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
     int[] arr = new int[m + n];
            //遍历短的那个，长的剩余的往后填
            int i = 0, j = 0, curr = 0;
            while (i < m || j < n) {
        
                if (i == m) {
        
                    curr = nums2[j];
                    j++;
                } else if (j == n) {
        
                    curr = nums1[i];
                    i++;
                } else if (nums1[i] < nums2[j]) {
        
                    curr = nums1[i];
                    i++;
                } else {
        
                    curr = nums2[j];
                    j++;
                }
                arr[i + j - 1] = curr;
            }
     
    
            //遍历nums1并赋值
            if (arr.length >= 0) {
        
                System.arraycopy(arr, 0, nums1, 0, arr.length);
            }
        }
    }

执行用时: **0 ms**

内存消耗: **38.6 MB**

### 3. 逆向双指针（齐姐思路） ###

**解题思路：**

题解 2 我们发现是从前向后定义双指针，我们定义了两个指针 i 和 j ，但是我们会发现，如果我们采取从后向前遍历（数组已经排好序），那么减少了变量的定义，而且 num1 的后半部分是空的，可以直接覆盖而不会影响结果。

那么每次遍历，num1 、 num2 的指针为 m-- 和 n–，我们将较大的那个数字复制到 num1 的后边，所以我们还需定义一个额外的指针来确定 num1 中将要插入的元素位置，使得每次复制元素后，指针向前移一位。

这里我们注意如果 num1 复制完了，我们还要看 num2 是否复制完，如果num2 复制完，就可以了，因为已经排好序了。

**代码：**

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
      //定义确定num1位置的指针
            int pos = m-- + n-- -1;
            while (m>=0 && n>=0){
        
                nums1[pos--] = nums1[m]>nums2[n]?nums1[m--]:nums2[n--];
            }
            //判断 num2 是否遍历完
            while (n>=0){
        
                nums1[pos--] = nums2[n--];
            }
        }
    }

执行用时: **0 ms**

内存消耗: **38.5 MB**

[gif1]: /images/20221005/e9b23b744f5d4113b499ac0f10433152.png