双指针算法-Two Pointers

发表于 | 分类于
字数统计: 2k

同向双指针

1. 滑动窗口问题

在一个长度为n的数组中，求满足条件的一段长度为k的子数组。

  • Window Sum
    给一个大小为n的整型数组和一个大小为k的滑动窗口，将滑动窗口从头移到尾，输出从开始到结束每一个时刻滑动窗口内的数的和。

  • Minimum Size Subarray Sum
    给定一个由 n个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。

  • Sliding Window Median
    给定一个包含 n 个整数的数组，和一个大小为k的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的中位数。
    使用两个Heap, 一个大根堆，一个小根堆。大根堆储存小于等于当前中位数的元素，小根堆储存比当前中位数大的元素。维持大根堆的大小等于小根堆，或比小根堆多1. 这样大根堆的堆顶就是当前窗口中的中位数了。

  • Sliding Window Maximum
    给出一个可能包含重复的整数数组，和一个大小为k的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

  • Minimum Window Substring
    给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的最短子串。

2. 快慢指针

在遍历链表的过程中，使用两个指针，其中一个比另一个的位置更靠前。

  • Linked List Cycle II
    给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。
    快慢指针，快指针一次走两步，慢指针走一步。当两指针相遇，则说明链表中有环。

相向双指针

1. 判断回文串

  • Valid Palindrome
    给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，忽略大小写。
    空串也是回文串

2. 两数和问题

  • Two Sum
    给一个整数数组，找到两个数使得他们的和等于一个给定的数target.
    – 方法1：枚举两个数，看它们的和是否等于target。
    – 时间复杂度：$O(n^2)$
    – 空间复杂度：$O(1)$
    – 方法2：遍历数组，用hashmap储存走过的数。如果target与当前数的差已经在hashmap中，返回这两个数的下标。
    – 时间复杂度：$O(n)$
    – 空间复杂度：$O(n)$
    – 方法3：用自定义类储存每个数的值与下标，将数组从小到大排列。左指针从数组头开始，右指针从数组尾开始。当左右指针指向的数的和小于target的时候，左指针右移一位；大于target的时候，右指针左移一位；等于target的时候返回下标。
    – 时间复杂度：$O(nlogn)$
    – 空间复杂度：$O(n)$
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
52
53
54
// HashMap
public int[] twoSum(int[] numbers, int target) {
	Map<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < numbers.length; i++) {
		if (map.containsKey(target - numbers[i])) {
			return new int[]{map.get(target - numbers[i]), i};
		} else {
			map.put(numbers[i], i);
		}
	}
	return new int[0];
}

// Two Pointers
public class Solution {
	class Node{
		int val, index;
		public Node(int val, int index) {
			this.val = val;
			this.index = index;
		}
	}
	public int[] twoSum(int[] numbers, int target) {
		// 构建自定义类，并排序。
		int n = numbers.length;
		Node[] nodes = new Node[n];
		for (int i = 0; i < n; i++) {
			nodes[i] = new Node(numbers[i], i);
		}
		Comparator<Node> nodeComparator = new Comparator<Node>(){
			@Override
			public int compare(Node n1, Node n2) {
				if (n1.val == n2.val) {
					return n1.index - n2.index;
				}
				return n1.val - n2.val;
			}
		};
		Arrays.sort(nodes, nodeComparator); 
		// 相向双指针查找目标解
		for (int l = 0, r = n - 1; l < r; r--) {
			while (l < r && nodes[l].val + nodes[r].val < target) {
				l++;
			}
			// 找到目标解
			if (nodes[l].val + nodes[r].val == target) {
				int[] res = new int[]{nodes[l].index, nodes[r].index};
				Arrays.sort(res);
				return res;
			}
		}
		return new int[0];
	}
}

  • Two Sum II - Input array is sorted
    给定一个已经按升序排列的数组，找到两个数使他们加起来的和等于特定数。
    函数应该返回这两个数的下标，index1必须小于index2。
    双指针算法，在O(n)时间内完成。

  • Two Sum - Unique Pairs
    给一整数数组, 找到数组中有多少组不同的元素对有相同的和, 且和为给出的 target 值, 返回对数。
    双指针算法，注意去重。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int twoSum(int[] nums, int target) {
    	if (nums == null || nums.length < 2) return 0;
    	int ans = 0;
    	Arrays.sort(nums); // 因为是计数的题目，可以直接将数组重排序而不记录下标
    	for (int l = 0, r = nums.length - 1; l < r; r--) {
    		while (l < r && nums[l] + nums[r] < target) {
    			l++;
    		}
    		if (l < r && nums[l] + nums[r] == target) {
    			ans++;
    			while (l < r && nums[r] == nums[r - 1]) {
    				r--; // 去重
    			}
    		}
    	}
    	return ans;
    }

  • Two Sum - Closest to target
    给定整数数组num，从中找到两个数字使得他们和最接近target，返回两数和与target的差的绝对值。
    每次移动左指针或右指针的时候，都要比较两数和与target的距离。

  • Two Sum - Less than or equal to target
    给定一个整数数组，找出这个数组中有多少对的和是小于或等于目标值。返回对数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int twoSum(int[] nums, int target) {
    	if(nums == null || nums.length < 2) return 0;
    	Arrays.sort(nums);
    	int ans = 0;
    	for (int l = 0, r = nums.length - 1; l < r; ) {
    		if (nums[l] + nums[r] <= target) {
    			ans += r - l; // 当前l下，所有小于r的数与l的和都满足条件
    			l++;
    		} else {
    			r--;
    		}
    	}
    	return ans;
    }

  • Two Sum - Greater than target
    给一组整数，问能找出多少对整数，他们的和大于一个给定的目标值。
    类似于上题。

  • Two Sum - Difference equals to target
    给定一个整数数组，找到两个数的差等于目标值。index1必须小于index2。
    和第一个Two Sum类似。
    HashMap解法：遍历到的每一个数可能是减数也可能是被减数。
    双指针解法：套模板就可以。

  • Three Sum
    给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
    转化为a + b = -c，变为two sum问题。注意去重。
    时间复杂度 - $O(n^2)$
    空间复杂度 - $O(1)$

    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
    public class Solution {
    	public List<List<Integer>> threeSum(int[] numbers) {
    		List<List<Integer>> ans = new ArrayList<>();
    		if (numbers == null || numbers.length < 3) return ans;
    		Arrays.sort(numbers);
    		for (int i = 0; i < numbers.length - 2; i++) {
    			if (i > 0 && numbers[i] == numbers[i - 1]) continue; // 去重
    			twoSum(numbers, -numbers[i], i + 1, ans);
    		}
    		return ans;
    	}
    	private void twoSum(int[] numbers, int target, int st, List<List<Integer>> ans) {
    		for (int l = st, r = numbers.length - 1; l < r; r--) {
    			while (l < r && numbers[l] + numbers[r] < target) {
    				l++;
    			}
    			if (l != r && numbers[l] + numbers[r] == target) {
    				List<Integer> item = Arrays.asList(-target, numbers[l], numbers[r]);
    				ans.add(item);
    				while (l < r && numbers[r] == numbers[r - 1]) {
    					r--; // 去重
    				}
    			}
    		}
    	}
    }

3. 分区问题

借鉴了快速排序的思想，双指针分区。

  • QuickSelect
    在数组中找到第 k 大的元素。(你可以交换数组中的元素的位置。)
    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
    public class Solution {
        public int kthLargestElement(int n, int[] nums) {
            return helper(nums, 0, nums.length - 1, n);
        }
        private int helper(int[] nums, int left, int right, int k) {
            int l = left, r = right;
            int pivot = nums[l];
            while (l <= r) {
                while (l <= r && nums[l] > pivot) {
                    l++;
                }
                while (l <= r && nums[r] < pivot) {
                    r--;
                }
                if (l <= r) {
                    int tmp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = tmp;
                    l++;
                    r--;
                }
            }
            // 第k大元素在左边
            if (left + k - 1 <= r) {
                return helper(nums, left, r, k);
            }
            // 第k大元素在右边
            if (left + k - 1 >= l) {
                return helper(nums, l, right, k - (l - left));
            }
            // 第k大元素在左右指针中间
            return nums[r + 1];
        }
    }