双指针


删除有序数组中的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

26 难度:easy

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 :

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int i = 0; //i指向新数组的最后一个元素下标
int j = 1;
while(j < n){
if(nums[i] == nums[j]){
j++;
continue;
}
if(j != i + 1){
nums[i + 1] = nums[j];
}
i++;
j++;
}
return i + 1;
}
}

双指针!原地覆盖!

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

删除有序数组中的重复项 II

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

80 难度:mid

与上一题一样,只不过这次要求每个元素 最多出现两次 ,返回删除后数组的新长度。

示例:
输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if(n <= 2) return n;
int i = 2; //待覆盖的位置
int j = 2; //一直移动的指针,相同就一直移动
while(j < n){
if(nums[i - 2] != nums[j]){
//这里的意思是直接保留前两个数,比较第三个数和第一个数是否相等,如果相等说明前3个元素都相等(数组有序),就移动j,抛弃这个元素,如果不相等,就将它覆盖到i所在的位置
nums[i] = nums[j];
i++;
}
j++;
}
return i;//覆盖过之后就i++了,所以i指向的是新数组的后一个元素,即i的大小是数组长度
}
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

删除排序链表中的重复元素II

82 难度 mid

给定一个已排序的链表的头 head删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表

示例1:

1->2->3->3->4->4->5 去重后为 1->2->5

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

迭代,一次遍历

因为头结点也可能被删除,所以需要使用虚拟头结点来跟踪最终的头结点

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode cur = dummyNode;
while(cur.next != null && cur.next.next != null){
if(cur.next.val == cur.next.next.val){
int x = cur.next.val;
while(cur.next != null && cur.next.val == x){
cur.next = cur.next.next;
}
}else{
cur = cur.next;
}
}
return dummyNode.next;
}
}

移除元素

https://leetcode-cn.com/problems/remove-element/

27 难度 easy

给定一个无序数组,需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int i = 0;
int j = 0;
while(j < n){
if(nums[j] != val){
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
}

这个方法和上面的方法基本上一样,都是将需要的元素放在数组的前面位置,即将不等于val的元素覆盖到前面,如果等于val,就跳过这个元素,搜索后面不等于val的元素,覆盖到上面。

i 指向需要被覆盖的元素的位置,j 来遍历数组元素

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

官方还有一个优化版,利用首尾指针,目的是当出现只有数组首元素等于val的时候,上述方法所有元素都要往前移动,复杂度高,所以可以利用首尾指针,直接将尾指针的元素覆盖到首指针就结束了。

但是我有一个疑问,待解决如果数组元素全都是val 那不是还得全部赋值到 i 的位置?这和首元素是val 全部覆盖耗费的时间一样呀?不懂哪里优化了


三数之和

https://leetcode-cn.com/problems/3sum/

15 难度:mid

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

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

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:
输入:nums = [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
27
28
29
30
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
//if(n == 0) return list;
for(int k = 0; k < n - 2; k++){
if(k != 0 && nums[k] == nums[k - 1]) continue;
int target = nums[k];
int j = n - 1;
for(int i = k + 1; i < n - 1; i++){
if(i != k + 1 && nums[i] == nums[i - 1]) continue;
while(i < j && nums[i] + nums[j] + target > 0){
j--;
}
if(i == j){
break;
}
if(nums[i] + nums[j] + target == 0){
List<Integer> arr = new ArrayList<>();
arr.add(nums[k]);
arr.add(nums[i]);
arr.add(nums[j]);
list.add(arr);
}
}
}
return list;
}
}

根据最接近的三数之和,又写了一个代码,我比较喜欢这个,但是这个比上面那个花费时间多2ms

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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
for(int k = 0; k < n - 2; k++){
if(nums[k] > 0) break;
if(k != 0 && nums[k] == nums[k - 1]) continue;
int j = n - 1;
int i = k + 1;
while(i < j){
int sum = nums[k] + nums[i] + nums[j];
if(sum > 0){
while(i < j && nums[j - 1] == nums[j]){
j--;
}
j--;
}else if(sum < 0){
while(i < j && nums[i + 1] == nums[i]){
i++;
}
i++;
}else{
List<Integer> arr = new ArrayList<>();
arr.add(nums[k]);
arr.add(nums[i]);
arr.add(nums[j]);
list.add(arr);
//因为找到一组,所以需要同时移动i,j
while(i < j && nums[i + 1] == nums[i]){//去重
i++;
}
i++;
while(i < j && nums[j - 1] == nums[j]){
j--;
}
j--;
//上面这段其实等价于
//while(i < j && nums[j] == nums[--j])
//--j是先进行j = j-1 ,然后再进行运算
}
}
}
return list;
}
}

首先需要先确保数组有序,原因是如果无序,则会遍历出重复的一组和为0的数。然后第一层for循环是遍历数组中所有不重复的元素,以它为新数组的首元素,来构造不同的和为零的数组。如果遇到重复的元素,就直接跳过,因为上一步已经遍历过了。然后是数组的第二个元素,指针从上层的后面开始,往右移动,第三个元素从末尾开始,往左移动。当有a+b+c=0后,随着b的增加,要想a+b’+c‘=0,那么一定有 c’ < c。所以c是从数组末尾向左移动。移动移动后…当b与c相等时,在以首元素开头的循环中不会再有和为零的元素了,需要进入新的首元素循环啦

举个栗子🌰

新数组的首元素即是-4,第二个元素从k+1开始,而第三个元素是从n-1开始,只有他们的和大于0时,说明 c 的值太大了,需要缩小,往左移动 j ,才有可能使和为0。而如果他们的和一开始就小于0,那肯定不会有更大的了,需要将 i 向右移动,然后再看是否有和大于等于0的一组数。


最接近的三数之和

https://leetcode-cn.com/problems/3sum-closest/

16 难度 mid

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

返回这三个数的和。假定每组输入只存在恰好一个解。

示例 1:

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

提示:

3 <= nums.length <= 1000

-1000 <= nums[i] <= 1000

-104 <= target <= 104

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
//当target等于负数的话,Integer.MAX_VALUE 减负数会越界,变成Integer.MIN_VALUE
for(int k = 0; k < n - 2; k++){
for(int i = k + 1; i < n; i++){
for(int j = i + 1; j < n - 1; j++){
int sum = nums[i] + nums[j] + nums[k];
if(sum == target){
return sum;
}
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
}
}
}
return best;
}
}

但是这个方法**时间复杂度是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
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
//当target等于负数的话,Integer.MAX_VALUE 减负数会越界,变成Integer.MIN_VALUE
for(int k = 0; k < n - 2; k++){
if(k != 0 && nums[k] == nums[k-1]) continue;
int knum = nums[k];
int j = n - 1;
int i = k + 1;
while(i < j){
int sum = nums[i] + nums[j] + knum;
if(sum == target){
return sum;
}
//看谁最接近target
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
if(sum > target){
//需要将j往左移动
int j0 = j - 1;
while(i < j0 && nums[j0] == nums[j]){
j0--;
}
j = j0;
}else{
//需要将i往右移动
int i0 = i + 1;
while(i0 < j && nums[i0] == nums[i]){
i0++;
}
i = i0;
}
}
}
return best;
}
}

一看到最接近,肯定是用差的绝对值来比较,三数的和与target的差的绝对值越小(最小为0),越接近target。我们先固定一个数a,假设下标是i,对剩下两个数用双指针由两端开始进行枚举,范围是【i+1,n-1】,由于数组已经进行了升序排序,a+b+c>=target 则需要减小c,即向左移动c,反之,a+b+c < target 则需要增加b,即向右移动b。

每一次枚举的过程中,我们尝试边界上的两个元素,根据它们与 target 的值的关系,选择「抛弃」左边界的元素还是右边界的元素,从而减少了枚举的范围。 —–LeetCode

有两个可以优化的地方。

  1. sum==target,直接返回即可
  2. 对于同一个移动的指针,如果移动的下一个数与移动前的数值相同,那么需要跳过,因为移动前的循环中其他变量都没变,相当于这个也没变,不用重复做了。
  • 时间复杂度:O(n²),for循环是O(n),while循环也是O(n)
  • 空间复杂度:O(log N)。排序

四数之和

https://leetcode-cn.com/problems/4sum/

18 难度 mid

给你一个由 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]]

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
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
List<List<Integer>> list = new ArrayList<>();
if(n < 4) return list;
Arrays.sort(nums);
for(int k = 0; k < n - 3; k++){
if(k != 0 && nums[k] == nums[k - 1]) continue;
// 如果这四数之和大于target, 往后算也必大于target
if ((long)nums[k] + nums[k + 1] + nums[k + 2] + nums[k + 3] > target) break;
// 下面这四数之和小于target, 则nums[i]小了
if ((long)nums[k] + nums[n - 3] + nums[n - 2] + nums[n -1] < target) continue;
for(int m = k + 1; m < n - 2; m++){
if(m != k + 1 && nums[m] == nums[m - 1]) continue;
// 如果这四数之和大于target, 往后算也必大于target
if ((long)nums[k] + nums[m] + nums[m + 1] + nums[m + 2] > target) break;
// 下面这四数之和小于target, 则nums[i]小了
if ((long)nums[k] + nums[m] + nums[n - 2] + nums[n -1] < target) continue;
int i = m + 1;
int j = n - 1;
while(i < j){
int sum = nums[i] + nums[j] + nums[k] + nums[m];
if(sum - target > 0){
while(i < j && nums[j] == nums[--j]);
}else if(sum - target < 0){
while(i < j && nums[i] == nums[++i]);
}else{
list.add(Arrays.asList(nums[k],nums[m],nums[i],nums[j]));
while(i < j && nums[j] == nums[--j]);
while(i < j && nums[i] == nums[++i]);
}
}
}
}
return list;
}
}

和三数之和一样的思路,只是多加了一层for循环,所以时间复杂度是O(n的三次方)

但是这个优化是我没想到的

// 如果这四数之和大于target, 往后算也必大于target

if ((long)nums[k] + nums[k + 1] + nums[k + 2] + nums[k + 3] > target) break;

// 下面这四数之和小于target, 则nums[i]小了

if ((long)nums[k] + nums[n - 3] + nums[n - 2] + nums[n -1] < target) continue;


合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

88 难度 easy

给你两个按 非递减顺序 (就是在数组nums1中,前m个元素是递增的,在数组nums2中,元素是递增的)排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

逆向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
while(j >= 0){
//i >=0 是防止nums1={0}的情况
//nums1={0}的话就直接将nums2全部赋值到nums1上
if(i >= 0 && nums1[i] > nums2[j]){
nums1[i + j + 1] = nums1[i];
i--;
}else{
nums1[i + j + 1] = nums2[j];
j--;
}
}
}
}

nums2数组优先,如果nums2数组为空时,直接就不用合并了,结束循环,但是nums1为空(指的是m=0)不一定

  • 时间复杂度:O(m + n)。指针移动单调递减,最多移动 m+n次。
  • 空间复杂度:O(1)。

实现strStr()

https://leetcode-cn.com/problems/implement-strstr/

28 难度 easy

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。

示例 1:

输入:haystack = “hello”, needle = “ll”
输出:2

要看needle是否存在于haystack中,就看haystack中有几个与needle长度相同的字符串,然后依次进行比较,只要一有不同的字符,就立刻开始下一次的比较,这样比较节约时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int strStr(String haystack, String needle) {
int m = haystack.length();
int n = needle.length();
for(int i = 0; i < m - n + 1; i++){
boolean flag = true;
for(int j = 0; j < n; j++){
if(haystack.charAt(i + j) != needle.charAt(j)){
flag = false;
break;
}
}
if(flag){
return i;
}
}
return -1;
}
}
  • 时间复杂度:O(m*n)
  • 空间复杂度:O(1)

还有一个KMP解法,后续学到了再看


删除排序链表中的重复元素

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

83 难度 easy

给定一个已排序的链表的头 head删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表

示例1:

1->1->2->3->3 去重后变为 1->2->3

输入:head = [1,1,2,3,3]
输出:[1,2,3]

提示:

  • 链表中节点数目在范围 [0, 300]
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode cur = head;
ListNode next = cur.next;
while(cur != null){
if(next == null){
cur.next = null;
break;
}
if(cur.val != next.val){
cur.next = next;
cur = cur.next;
}
next = next.next;
}
return head;
}
}
  • 时间复杂度:O(n)O(n),其中 nn 是链表的长度。
  • 空间复杂度:O(1)O(1)。

没有用双指针的解法(官方用的这个解法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode cur = head;
while(cur.next != null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}


双指针
https://vickkkyz.fun/2022/03/24/计算机/LeetCoode/双指针/
作者
Vickkkyz
发布于
2022年3月24日
许可协议