LeetCode - 双指针

PS：按照代码随想录的题单顺序刷题，记录一下。

1. 移除元素

1.1 移除元素

描述

LeetCode27 - 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。简单

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]

思路

使用双指针，右指针指向数组尾部，左指针从前往后遍历，一旦元素等于目标值就交换元素值，右指针左移，当左指针大于右指针时结束循环。

27 - 移除元素

var removeElement = function(nums, val) {
    let left = 0, right = nums.length - 1;
    while(left <= right) {
        if(nums[left] === val) {
            nums[left] = nums[right];
            nums[right] = val;
            right--;
            continue;
        }
        left++;
    }
    return left;
};

1.2 删除排序数组中的重复项

描述

LeetCode26 - 给你一个非严格递增排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。简单

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k。

示例1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

示例2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

思路

快慢指针，如果慢指针与快指针元素不一样，则可以赋值。

26 - 删除排序数组中的重复项

var removeDuplicates = function(nums) {
    let slow = 0, fast = 1;
    while(fast < nums.length) {
        if(nums[slow] !== nums[fast]) {
            nums[++slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
};

1.3 移动零

描述

LeetCode283 - 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意，必须在不复制数组的情况下原地对数组进行操作。简单

示例1：

输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

示例2：

输入：nums = [0]
输出：[0]

思路

把 0 移到末尾，换个思路，从头先把非 0 元素排好，剩下的全部置 0，快慢指针，与前面题目类似。

283 - 移动零

var moveZeroes = function(nums) {
    let slow = 0, fast = 0;
    while(fast < nums.length) {
        if(nums[fast] !== 0) {
            nums[slow++] = nums[fast];
        }
        fast++;
    }
    while(slow < nums.length) {
        nums[slow++] = 0; 
    }
};

1.4 比较含退格的字符串

描述

LeetCode844 - 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。简单

注意：如果对空文本输入退格字符，文本继续为空。

示例1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

思路

这题用栈比较简单，如果想空间复杂度 O(1) 可以用双指针，就是两个字符串从后往前遍历，遇到 # 就表示前一个字符需要被删除，每次找到两个字符串不会被删除的字符进行比较。

844 - 比较含退格的字符串

var backspaceCompare = function(s, t) {
    let sNum = 0, tNum = 0;
    let sIndex = s.length - 1, tIndex = t.length - 1;
    while(sIndex > -1 || tIndex > -1) {
        while(sIndex > -1) {
            if (s[sIndex] === '#') {
                sNum++;
            } else if(sNum > 0) {
                sNum--;
            } else {
                break;
            }
            sIndex--;
        }
        while(tIndex > -1) {
            if(t[tIndex] === '#') {
                tNum++;
            } else if(tNum > 0) {
                tNum--;
            } else {
                break;
            }
            tIndex--;
        }
        if(sIndex < 0 && tIndex < 0) {
            return true;
        } else if (sIndex > -1 && tIndex > -1) {
            if(s[sIndex] === t[tIndex]) {
                sIndex--;
                tIndex--;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    return true;
};

1.5 有序数组的平方

描述

LeetCode977 - 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。简单

示例1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路

使用双指针比较两端元素绝对值大小，将大的元素的平方逆序存入数组，指针向中间移动。

977 - 有序数组的平方

var sortedSquares = function(nums) {
    let left = 0, right = nums.length - 1;
    const res = new Array(nums.length);
    for(let i = nums.length - 1; i > -1; i--) {
        if(Math.abs(nums[left]) >= Math.abs(nums[right])) {
            res[i] = nums[left] * nums[left];
            left++;
        } else {
            res[i] = nums[right] * nums[right];
            right--;
        }
    }
    return res;
};

2. 反转字符串

描述

LeetCode344 - 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。简单

示例1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

思路

使用双指针，从头尾向中间移动，同时交换元素。

344 - 反转字符串

var reverseString = function(s) {
    let left = 0, right = s.length - 1;
    while(left < right) {
        let temp = s[right];
        s[right] = s[left];
        s[left] = temp;
        left++;
        right--;
    }
};

3. 反转字符串里的单词

描述

LeetCode151 - 给你一个字符串 s，请你反转字符串中单词的顺序。中等

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例1：

输入：s = " the sky is blue"
输出："blue is sky the"

思路

首先去掉首尾空格，再从后往前遍历存入数组，需要注意中间多个空格的情况，最后翻转每个单词。

151 - 反转字符串里的单词

var reverseWords = function (s) {
    const result = [];
    const n = s.length;
    let left = 0, right = n - 1;
    // 去掉首尾空格
    while (s[left] == ' ') {
        left++;
    }
    while (s[right] == ' ') {
        right--;
    }
    // 从后往前遍历，存入数组
    while (left <= right) {
        // 过滤中间重复空格
        if(s[right] === ' ') {
            if (right > 0 && s[right - 1] == ' ') {
                right--;
                continue;
            }
        }
        result.push(s[right]);
        right--;
    }
    // 反转单词
    let start = 0;
    for(let i = 0; i < result.length; i++) {
        if(result[i] === ' ') {
            reverseStr(result, start, i - 1);
            start = i + 1;
        }
    }
    reverseStr(result, start, result.length - 1);
    return result.join('')
};

const reverseStr = (arr, left, right) => {
    while (left < right) {
        const temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
        left++;
        right--;
    }
}

4. 反转链表

描述

LeetCode206 - 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。简单

示例1：

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

思路

构造个新链表，依次遍历并将元素插入新链表的第一个位置。

双指针：使用两个指针分别保存上一元素和下一元素。

206 - 反转链表

var reverseList = function(head) {
    if(!head) return null;
    let list = new ListNode(head.val, null);
    let current = head.next;
    while(current) {
        const node = new ListNode(current.val, null);
        node.next = list;
        list = node;
        current = current.next;
    }
    return list;
};

// 双指针
var reverseList = function(head) {
    if(!head) return head;
    let prev = null, after, current = head;
    while(current) {
        after = current.next;
        current.next = prev;
        prev = current;
        current = after;
    }
    return prev;
};

5. 删除链表的倒数第 N 个结点

描述

LeetCode19 - 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。中等

示例1：

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

示例2：

输入：head = [1], n = 1
输出：[]

思路

定义双指针，右指针先前进 n 步，左指针再跟着遍历，当右指针遍历到末尾时，左指针指向的就是要删除的元素的前一节点。大多数链表题可以设置虚拟头节点，便于操作。

19 - 删除链表的倒数第 N 个结点

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    dummy.next = head;
    // 双指针
    let left = dummy, right = dummy;
    for(i = 0; i < n; i++) {
        right = right.next;
    }
    while(right.next) {
        right = right.next;
        left = left.next
    }
    left.next = left.next.next;
    return dummy.next;
};

6. 相交链表

描述

LeetCode160 - 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。简单

示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路

哈希表：使用哈希表存储一个链表的元素，遍历另一链表判断是否有相同节点。

双指针：分别遍历两个链表并比较，到达最后一个元素将指针指向另一个链表。

160 - 相交链表

// 双指针
var getIntersectionNode = function (headA, headB) {
    let currentA = headA, currentB = headB;
    let transforA = true, transforB = true;
    while (currentA && currentB) {
        if (currentA === currentB) {
            return currentA;
        }
        currentA = currentA.next;
        currentB = currentB.next;
        if (transforA && !currentA) {
            currentA = headB;
            transforA = false;
        }
        if(transforB && !currentB) {
            currentB = headA;
            transforB = false;
        }
    }
    return null;
};

// 哈希表
var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    let current = headA;
    while(current) {
        map.set(current, 1);
        current = current.next;
    }
    current = headB;
    while(current) {
        if(map.has(current)) {
            return current;
        }
        current = current.next;
    }
    return null;
};

7. 环形链表II

描述

LeetCode142 - 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。中等

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。pos 表示尾部指向的节点索引，为 -1 表示无环。

思路

首先想到的就是用哈希表或集合将遍历过的节点保存，时间和空间复杂度都是 O(n)。还有个快慢指针版本，其中快指针每次走两步，慢指针每次一步，二者必定会在环内相遇（这里可能不好理解），经过数学推理可以得出，慢指针从环内相遇点继续向下走，同时用第三个指针从头指针开始出发，二者相遇的节点就是开始入环的节点。

142 - 环形链表II

// 哈希表
var detectCycle = function(head) {
    const map = new Map();
    let current = head;
    while(current) {
        if (map.get(current)) {
            return current;
        }
        map.set(current, 1);
        current = current.next;
    }
    return null;
};

// 快慢指针
var detectCycle = function(head) {
    if (!head) return null;
    let slow = head, fast = head;
    while(fast) {
        slow = slow.next;
        if(!fast.next) {
            return null;
        } else {
            fast = fast.next.next;
        }
        if(fast === slow) {
            let cur = head;
            while(cur !== slow) {
                cur = cur.next;
                slow = slow.next;
            }
            return cur;
        }
    }
    return null;
};

8. 三数之和

描述

LeetCode15 - 给你一个整数数组 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]]

思路

排序+双指针。首先排序，第一层 for 遍历，每次遍历使用 left 指向 i 的后一元素，right 指向最后一个元素，不停移动指针，将符合条件的元素加入结果。本次遍历结束后判断下一位置是否与当前相等，相等则 i++，这步是防止出现重复三元组。

15 - 三数之和

var threeSum = function(nums) {
  const n = nums.length;
  // 先排序
  nums.sort((a, b) => a - b);
  let left, right;
  const res = [];
  for(let i = 0; i < nums.length - 2; i++) {
    left = i + 1, right = n - 1;
    // 剪枝
    if(nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
    if(nums[i] + nums[n - 1] + nums[n - 2] < 0) continue;
    while(left < right) {
      if(nums[left] + nums[right] === -nums[i]) {
        res.push([nums[i], nums[left], nums[right]]);
        left++;
        // 去重
        while(nums[left] === nums[left - 1]) left++;
        right--;
        while(nums[right] === nums[right + 1]) right--;
      } else if (nums[left] + nums[right] > -nums[i]) {
        right--;
        while(nums[right] === nums[right + 1]) right--;
      } else {
        left++;
        while(nums[left] === nums[left - 1]) left++;
      }
    }
    // 去重
    while(nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return res;
};

9. 四数之和

描述

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

思路

思路跟三数之和类似，首先两个 for 循环确定两个元素，然后用双指针探测另外两个值，期间可以进行剪枝优化。

18 - 四数之和

var fourSum = function(nums, target) {
  const res = [];
  const n = nums.length;
  let left, right;
  // 排序
  nums.sort((a, b) => a - b);
  for(let i = 0; i < n - 3; i++) {
    // 剪枝
    if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
    if(nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

    for(let j = i + 1; j < n - 2; j++) {
      // 剪枝
      if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
      if(nums[i] + nums[j] + nums[n - 1] + nums[n -2] < target) continue;

      left = j + 1, right = n - 1;
      let need = target - nums[i] - nums[j];
      while(left < right) {
        if(nums[left] + nums[right] === need) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          left++;
          while(nums[left] === nums[left - 1]) left++;
          right--;
          while(nums[right] === nums[right + 1]) right--;
        } else if(nums[left] + nums[right] > need) {
          right--;
          while(nums[right] === nums[right + 1]) right--;
        } else {
          left++;
          while(nums[left] === nums[left - 1]) left++;
        }
      }
      while(nums[j] === nums[j + 1]) {
        j++;
      }
    }
    while(nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return res;
};