双指针

说明

前置知识：无

设置两个指针的技巧，其实这种说法很宽泛，似乎没什么可总结的

1）有时候所谓的双指针技巧，就单纯是代码过程用双指针的形式表达出来而已。

没有单调性（贪心）方面的考虑

2）有时候的双指针技巧包含单调性（贪心）方面的考虑，牵扯到可能性的取舍。

对分析能力的要求会变高。其实是先有的思考和优化，然后代码变成了双指针的形式。

3）所以，双指针这个“皮”不重要，分析题目单调性（贪心）方面的特征，这个能力才重要。

常见的双指针类型：

  • 同向双指针
  • 快慢双指针
  • 从两头往中间的双指针
  • 其他

左右指针

  • 左右双指针通常用于解决数组或字符串相关问题，例如寻找两数之和、反转字符串等。
  • 典型应用：求解数组或字符串相关问题。左右双指针可以在不同方向上同时进行移动，并通过特定条件来更新左右边界。

快慢指针

  • 快慢指针法通常用于解决链表中的问题，如判定链表中是否有环、找到链表的中间节点等。快指针每次移动两步，慢指针每次移动一步。
  • 典型应用：判断链表是否有环。当存在环时，快慢指针最终会相遇；找到链表中间节点时，快指针到达末尾时慢指针正好在中间位置。

总结来说，在编程中使用双指针法可帮助我们降低时间复杂度，并且适合处理循环、交错等特殊情况。

905. Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

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

思路

双指针

Time Complexity: O(N)

C++解法

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        for(int i = 0, j = 0; j < nums.size(); j++){
            if(nums[j] % 2 == 0){
                swap(nums[i++], nums[j]);
            }
        }
        return nums;
    }
};

Java解法

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        for (int i = 0, j = 0; j < nums.length; j++)
            if (nums[j] % 2 == 0) {
                int tmp = nums[i];
                nums[i++] = nums[j];
                nums[j] = tmp;;
            }
        return nums;
    }
}

922. Sort Array By Parity II

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]
Output: [2,3]

Constraints:

  • 2 <= nums.length <= 2 * 10^4
  • nums.length is even.
  • Half of the integers in nums are even.
  • 0 <= nums[i] <= 1000

Follow Up: Could you solve it in-place?

思路

双指针

C++解法

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        for(int odd = 1, even = 0; odd < nums.size() && even < nums.size(); ){
            if(nums[nums.size() - 1] % 2 != 0){
                swap(nums[odd], nums[nums.size() - 1]);
                odd += 2;
            }else{
                swap(nums[even], nums[nums.size() - 1]);
                even += 2;
            }
        }
        return nums;
    }
};

Java解法

// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
public class Code01_SortArrayByParityII {

	// 时间复杂度O(n)，额外空间复杂度O(1)
	public static int[] sortArrayByParityII(int[] nums) {
		int n = nums.length;
		for (int odd = 1, even = 0; odd < n && even < n;) {
			if ((nums[n - 1] & 1) == 1) {
				swap(nums, odd, n - 1);
				odd += 2;
			} else {
				swap(nums, even, n - 1);
				even += 2;
			}
		}
		return nums;
	}

	public static void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

}

287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

  • How can we prove that at least one duplicate number must exist in nums?
  • Can you solve the problem in linear runtime complexity?

思路

快慢指针（类似循环链表）

C++解法

数组记录数量：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        vector<int> result(100001, 0);
        for(int num : nums){
            result[num]++;
            if(result[num] > 1){
                return num;
            }
        }
        return -1;
    }
};

Java解法

// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
public class Code02_FindTheDuplicateNumber {

	// 时间复杂度O(n)，额外空间复杂度O(1)
	public static int findDuplicate(int[] nums) {
		if (nums == null || nums.length < 2) {
			return -1;
		}
		int slow = nums[0];
		int fast = nums[nums[0]];
		while (slow != fast) {
			slow = nums[slow];
			fast = nums[nums[fast]];
		}
		// 相遇了，快指针回开头
		fast = 0;
		while (slow != fast) {
			fast = nums[fast];
			slow = nums[slow];
		}
		return slow;
	}

}

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

思路

方法一：单调栈

方法二：双指针

C++解法

单调栈解法

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;
        int result = 0;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < height.size(); i++){
            if(height[i] < height[st.top()]){
                st.push(i);
            }else if(height[i] == height[st.top()]){
                st.push(i);
            }else{
               while(!st.empty() && height[i] > height[st.top()]){
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()){
                        int h = min(height[i], height[st.top()]) - height[mid];
                        int w = i - st.top() - 1;
                        result += h * w;
                    }
               }
               st.push(i);
            }
        }
        return result;
    }
};

Java解法

双指针解法：

// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
public class Code03_TrappingRainWater {

	// 辅助数组的解法（不是最优解）
	// 时间复杂度O(n)，额外空间复杂度O(n)
	// 提交时改名为trap
	public static int trap1(int[] nums) {
		int n = nums.length;
		int[] lmax = new int[n];
		int[] rmax = new int[n];
		lmax[0] = nums[0];
		// 0~i范围上的最大值，记录在lmax[i]
		for (int i = 1; i < n; i++) {
			lmax[i] = Math.max(lmax[i - 1], nums[i]);
		}
		rmax[n - 1] = nums[n - 1];
		// i~n-1范围上的最大值，记录在rmax[i]
		for (int i = n - 2; i >= 0; i--) {
			rmax[i] = Math.max(rmax[i + 1], nums[i]);
		}
		int ans = 0;
		//   x              x
		//   0 1 2 3...n-2 n-1
		for (int i = 1; i < n - 1; i++) {
			ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - nums[i]);
		}
		return ans;
	}

	// 双指针的解法（最优解）
	// 时间复杂度O(n)，额外空间复杂度O(1)
	// 提交时改名为trap
	public static int trap2(int[] nums) {
		int l = 1, r = nums.length - 2, lmax = nums[0], rmax = nums[nums.length - 1];
		int ans = 0;
		while (l <= r) {
			if (lmax <= rmax) {
				ans += Math.max(0, lmax - nums[l]);
				lmax = Math.max(lmax, nums[l++]);
			} else {
				ans += Math.max(0, rmax - nums[r]);
				rmax = Math.max(rmax, nums[r--]);
			}
		}
		return ans;
	}

}

881. Boats to Save People

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints:

  • 1 <= people.length <= 5 * 10^4
  • 1 <= people[i] <= limit <= 3 * 10^4

思路

排序+双指针

C++解法

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int left = 0;
        int right = people.size() - 1;
        int result = 0;
        int sum = 0;
        while(left <= right){
            sum = left == right ? people[left] : people[left] + people[right];
            if(sum > limit){
                right--;
            }else{
                left++;
                right--;
            }
            result++;
        }
        return result;
    }
};

Java解法

// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
public class Code04_BoatsToSavePeople {

	// 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
	public static int numRescueBoats(int[] people, int limit) {
		Arrays.sort(people);
		int ans = 0;
		int l = 0;
		int r = people.length - 1;
		int sum = 0;
		while (l <= r) {
			sum = l == r ? people[l] : people[l] + people[r];
			if (sum > limit) {
				r--;
			} else {
				l++;
				r--;
			}
			ans++;
		}
		return ans;
	}

}

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

思路

双指针解法计算公式：result = max(result, min(leftMax, rightMax) * (right - left))

C++解法

class Solution {
    public int maxArea(int[] height) {
        int result = 0;
        int left = 0; 
        int right = height.length - 1;
        while(left <= right){
            result = Math.max(result, Math.min(height[right],height[left])*(right-left));
            if(height[right] < height[left]) right--;
            else left++;
        }
        return result;
    }
}

Java解法

// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
public class Code05_ContainerWithMostWater {

	// 时间复杂度O(n)，额外空间复杂度O(1)
	public static int maxArea(int[] height) {
		int ans = 0;
		for (int l = 0, r = height.length - 1; l < r;) {
			ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
			if (height[l] <= height[r]) {
				l++;
			} else {
				r--;
			}
		}
		return ans;
	}

}

475. Heaters

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range. 

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

Example 1:

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Example 3:

Input: houses = [1,5], heaters = [2]
Output: 3

Constraints:

  • 1 <= houses.length, heaters.length <= 3 * 10^4
  • 1 <= houses[i], heaters[i] <= 10^9

思路

双指针，排序两个数组，然后为每间房子匹配最近的供暖器，计算最短距离的最大值。

C++解法

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int result = 0;
        for(int i = 0, j = 0; i < houses.size(); i++){
            while(!isBest(houses, heaters, i, j)){
                j++;
            }
            result = max(result, abs(houses[i] - heaters[j]));
        }
        return result;
    }

    bool isBest(vector<int>& houses, vector<int>& heaters, int i, int j){
        if(j == heaters.size() - 1 || abs(houses[i] - heaters[j]) < abs(houses[i] - heaters[j + 1])){
            return true;
        }
        return false;
    }
};

Java解法

// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
public class Code06_Heaters {

	// 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
	public static int findRadius(int[] houses, int[] heaters) {
		Arrays.sort(houses);
		Arrays.sort(heaters);
		int ans = 0;
		for (int i = 0, j = 0; i < houses.length; i++) {
			// i号房屋
			// j号供暖器
			while (!best(houses, heaters, i, j)) {
				j++;
			}
			ans = Math.max(ans, Math.abs(heaters[j] - houses[i]));
		}
		return ans;
	}

	// 这个函数含义：
	// 当前的地点houses[i]由heaters[j]来供暖是最优的吗？
	// 当前的地点houses[i]由heaters[j]来供暖，产生的半径是a
	// 当前的地点houses[i]由heaters[j + 1]来供暖，产生的半径是b
	// 如果a < b, 说明是最优，供暖不应该跳下一个位置
	// 如果a >= b, 说明不是最优，应该跳下一个位置
	public static boolean best(int[] houses, int[] heaters, int i, int j) {
		return j == heaters.length - 1 
				||
			   Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);
	}

}

41. First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

思路

left满足nums[left] == left + 1的最大下标

right可能满足nums[left] == left + 1的最大下标，右侧为垃圾区

C++解法

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int left = 0;
        int right = nums.size();
        while(left < right){
            if(nums[left] == left + 1) left++;
            else if(nums[left] > right || nums[left] <= left || nums[nums[left] - 1] == nums[left]){
                swap(nums[left], nums[right - 1]);
                right--;
            }else{
                swap(nums[left], nums[nums[left] - 1]);
            }
            
        }
        return left + 1;
    }
};

Java解法

// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
public class Code07_FirstMissingPositive {

	// 时间复杂度O(n)，额外空间复杂度O(1)
	public static int firstMissingPositive(int[] arr) {
		// l的左边，都是做到i位置上放着i+1的区域
		// 永远盯着l位置的数字看，看能不能扩充(l++)
		int l = 0;
		// [r....]垃圾区
		// 最好的状况下，认为1~r是可以收集全的，每个数字收集1个，不能有垃圾
		// 有垃圾呢？预期就会变差(r--)
		int r = arr.length;
		while (l < r) {
			if (arr[l] == l + 1) {
				l++;
			} else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
				swap(arr, l, --r);
			} else {
				swap(arr, l, arr[l] - 1);
			}
		}
		return l + 1;
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}