数组-双指针应用

EricYuan 收录于类别 Algorithm 和系列 Trick 阅读量次

2024-02-16 2024-02-16 约 387 字预计阅读 2 分钟

系列 -

数组双指针

双指针，一般两种，快慢指针和左右指针，根据不同场景使用不同方法。

以下题基本都是简单题，知道使用双指针就没啥难度了~

lc.167 两数之和 II - 有序数组

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
    let left = 0,
        right = numbers.length - 1
    while (left < right) {
        if (numbers[left] + numbers[right] < target) {
            left++
        } else if (numbers[left] + numbers[right] > target) {
            right--
        } else if (numbers[left] + numbers[right] === target) {
            return [left + 1, right + 1]
        }
    }
}

lc.26 删除有序数组中的重复项

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
    let left = 0,
        right = 1
    while (right < nums.length) {
        if (nums[left] === nums[right]) {
            right++
        } else {
            nums[++left] = nums[right++]
        }
    }
    return left + 1
}

lc.27 移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
    let left = 0,
        right = nums.length - 1
    while (left <= right) {
        if (nums[left] === val) {
            nums[left] = nums[right]
            right--
        } else {
            left++
        }
    }
    return left
}

lc.283 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let left = 0,
        right = 0
    while (right < nums.length) {
        if (nums[right] !== 0) {
            ;[nums[left++], nums[right++]] = [nums[right], nums[left]]
        } else {
            right++
        }
    }
}

lc.344 反转字符串

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    let left = 0,
        right = s.length - 1
    while (left <= right) {
        ;[s[left++], s[right--]] = [s[right], s[left]]
    }
}

lc.6 最长回文子串

回文子串的自身上，基本都是用双指针，比如：

判断是否是回文子串，两边往中间走
寻找回文子串，中间往两边走，只不过需要注意，这里的中间，要看字符是奇数还是偶数，所以一般两种情况都要考虑

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const getPalindrome = (s, l, r) => {
        while (l >= 0 && r < s.length && s[l] == s[r]) {
            l--
            r++
        }
        return s.substring(l + 1, r)
    }
    let res = ''
    for (let i = 0; i < s.length; ++i) {
        const s1 = getPalindrome(s, i, i)
        const s2 = getPalindrome(s, i, i + 1)
        res = res.length > s1.length ? res : s1
        res = res.length > s2.length ? res : s2
    }
    return res
}

这道题也可以用动态规划的方式来做，但是那样空间复杂度将为 O(n^2)

目录