双指针技巧|数组篇刷题合集

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums.length===0) return 0;//判断数组为空
    let fast=slow=0;
    while(fast<nums.length){//快慢指针
        if(nums[fast]!=nums[slow]){
            slow++;
            nums[slow]=nums[fast];
        }
        fast++;
    }
    return slow +1;
};

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(!head) return null;
    let slow=fast=head;
    while(fast){
        if(fast.val!==slow.val){
            slow.next=fast;
            slow=slow.next;
        }
        fast=fast.next;
    }
    slow.next=null;
    return head;
};

27. 移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let fast=slow=0;
    while(fast<nums.length){//注意是跟val比，slow的作用是保存下标的索引位置
        if(nums[fast]!==val){//保证nums[0..slow-1]是不包含值为val的元素
            nums[slow]=nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
};

283. 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let fast=0;
    let slow=0;
    while(fast<nums.length){//保证nums[0..slow-1]是不包含值为0的元素
        if(nums[fast]!==0){
            nums[slow]=nums[fast];
            slow++;
        }
        fast++;
    }
    for(; slow<nums.length;){
        nums[slow++]=0;
    }
};

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){
        let sum=numbers[left]+numbers[right];
        if(sum===target){
            return [left+1,right+1];
        }
        else if(sum<target){
            left++;
        }
        else{
            right--;
        }
        
    }   
};

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){
        let temp=s[left];
        s[left]=s[right];
        s[right]=temp;
        left++;
        right--;
    }   
};

5. 最长回文子串

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res='';
    for(let i=0;i<s.length;i++){
        let s1=Findmax(s,i,i);//奇数
        let s2=Findmax(s,i,i+1);//偶数
        if(s1.length>res.length) res=s1;
        res=res.length > s2.length ? res:s2;   
    }
    return res;

};

function Findmax(s,l,r){//l与r相等则表示基数，l与r不等则偶数 
    //从中心扩散找最长子串  
    while(l>=0 && r<s.length && s[l]===s[r]){
        l--;
        r++;
    }
    return s.slice(l+1,r)//左闭右开
}

剑指 Offer II 020. 回文子字符串的个数

/**
 * @param {string} s
 * @return {number}
 */

var countSubstrings = function(s) {
    let count=0;
    for(let i=0;i<s.length;i++){//字符串的每个字符都作为回文中心进行判断，中心是一个字符或两个字符
        count+=Findmax(s,i,i);
        count+=Findmax(s,i,i+1);
    }
    return count;    
};




function Findmax(s,l,r){//注意while边界判断 
    //从中心扩散找子串
    let count=0;  
    while(l>=0 && r<s.length && s[l]===s[r]){
        l--;
        r++;
        count++;
    }
    return count;
}

https://mp.weixin.qq.com/s/Z-oYzx9O1pjiym6HtKqGIQ