大廠算法面試之leetcode精講19.數(shù)組

視頻講解（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)

目錄：

1.開(kāi)篇介紹

2.時(shí)間空間復(fù)雜度

3.動(dòng)態(tài)規(guī)劃

4.貪心

5.二分查找

6.深度優(yōu)先&廣度優(yōu)先

7.雙指針

8.滑動(dòng)窗口

9.位運(yùn)算

10.遞歸&分治

11剪枝&回溯

12.堆

13.單調(diào)棧

14.排序算法

15.鏈表

16.set&map

17.棧

18.隊(duì)列

19.數(shù)組

20.字符串

21.樹(shù)

22.字典樹(shù)

23.并查集

24.其他類型題

數(shù)組操作的時(shí)間復(fù)雜度

• Access：O(1)

• Search：O(n)

• Insert： 平均O(n)，最好的情況下O(1)，也就是在數(shù)組尾部插入O(1)，最壞的情況下O(n)

• Delete；平均O(n)，最好的情況下O(1)，也就是在數(shù)組尾部刪除O(1)，最壞的情況下O(n)

ds_13

283. 移動(dòng)零 (easy)

動(dòng)畫(huà)過(guò)大，點(diǎn)擊查看

方法1:兩次遍歷

• 思路：遍歷數(shù)組，定義索引j為數(shù)組的第一個(gè)位置，遇上非0元素，讓j位置上的元素等于這個(gè)非0元素，遍歷完數(shù)組之后，j位置之后的元素全部置為0
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var moveZeroes = function (nums) {
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {//遇到非0元素，讓nums[j] = nums[i]，然后j++
            nums[j] = nums[i];
            j++;
        }
    }
    for (let i = j; i < nums.length; i++) {//剩下的元素全是0
        nums[i] = 0;
    }
    return nums;
};

java：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];
            }
        }
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0;
        }
    }
}   

方法2:雙指針一次遍歷

• 思路：定義left、right指針，right從左往右移動(dòng)，遇上非0元素，交換left和right對(duì)應(yīng)的元素，交換之后left++
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var moveZeroes = function(nums) {
    let left=0,right=0
    while(right<nums.length){
        if(nums[right]!==0){//遇上非0元素，交換left和right對(duì)應(yīng)的元素
            swap(nums,left,right)
            left++//交換之后left++
        }
        right++
    }
};
function swap(nums,l,r){
    let temp=nums[r]
    nums[r]=nums[l]
    nums[l]=temp
}

java：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}   

75. 顏色分類 （medium）

動(dòng)畫(huà)過(guò)大，點(diǎn)擊查看

方法1.雙指針

• 思路：準(zhǔn)備p0，p1兩個(gè)指針，p0指向0元素，p1指向1，初始化的時(shí)候，兩個(gè)指針都指向數(shù)組的第一個(gè)位置。然后循環(huán)數(shù)組
  1. 遇見(jiàn)1就交換當(dāng)前元素和p1，讓p1加1，向前移動(dòng)一位
  2. 遇見(jiàn)0就交換當(dāng)前元素和p0，如果p1小于p0，則此時(shí)p0指向的元素是1，與i位置元素交換之后 這個(gè)交換過(guò)去的1位置就不對(duì)了，所以交換過(guò)去的1需要在和p1交換一下，這時(shí)p0和p1都指向了正確的元素，所以都需要向前移動(dòng)一次。如果p0等于p1，則前面的元素都是0，所以p0和p1也要向前移動(dòng)一次
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，n是數(shù)組的長(zhǎng)度，空間復(fù)雜O(1)

js：

var sortColors = function (nums) {
    let p0 = 0 //指向0
    let p1 = 0 //指向0

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {//如果當(dāng)前i指向的元素等于1，則交換當(dāng)前元素和p1指向的元素
            let temp = nums[p1]
            nums[p1] = nums[i]
            nums[i] = temp
            p1++
        } else if (nums[i] === 0) {//如果當(dāng)前i指向的元素等于0，則交換當(dāng)前元素和p0指向的元素
            let temp = nums[p0]
            nums[p0] = nums[i]
            nums[i] = temp
            //如果p0小于p1 則此時(shí)p0指向的元素是1，與i位置元素交換之后 這個(gè)交換過(guò)去的1位置就不對(duì)了 所以交換過(guò)去的1需要在和p1交換一下
            if (p0 < p1) {
                temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
            }
            //每次交換0之后都要移動(dòng)p0和p1，如果p0===p1，則前面都是0，如果p0<p1,前面的代碼已經(jīng)交換了兩次
            p0++
            p1++
        }
    }
};

java

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}

方法2.雙指針

• 思路：準(zhǔn)備兩指針，p0指向元素0，它左邊的都是0，p2指向2，它右邊都是2，然后循環(huán)數(shù)組，當(dāng)循環(huán)到了p2，說(shuō)明p2右邊的元素都是正確的數(shù)，所以i<=p2
  1. 如果此時(shí)i指向元素2 i小于p2 則不斷交換p2和i指向的元素 因?yàn)榻粨Q過(guò)來(lái)的數(shù)可能還是2，那這個(gè)2就處于不正確的位置了
  2. 如果此時(shí)i指向元素0 則交換p0和i指向的元素
  3. 循環(huán)完成則0和2都拍好了，中間的1自然也是正確的位置
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，n是數(shù)組的長(zhǎng)度，空間復(fù)雜O(1)

js：

var sortColors = function (nums) {
    let p0 = 0;//指向0
    let p2 = nums.length - 1;//指向2
    for (let i = 0; i <= p2; i++) {//當(dāng)循環(huán)到了p2 說(shuō)明p2右邊的元素都是正確的數(shù)，所以i<=p2
        //如果此時(shí)i指向元素2 i小于p2 則不斷交換p2和i指向的元素 因?yàn)榻粨Q過(guò)來(lái)的數(shù)可能還是2，那這個(gè)2就處于不正確的位置了
        while (nums[i] === 2 && i < p2) {
            let temp = nums[i];
            nums[i] = nums[p2];
            nums[p2] = temp;
            p2--;
        }
        //如果此時(shí)i指向元素0 則交換p0和i指向的元素
        if (nums[i] === 0) {
            let temp = nums[i];
            nums[i] = nums[p0];
            nums[p0] = temp;
            p0++;
        }
    }
};

//寫(xiě)法2
var sortColors = function (nums) {
    const swap = (list, p1, p2) => [list[p1], list[p2]] = [list[p2], list[p1]]
    let red = 0,
        blue = nums.length - 1,
        p = 0

    while (p <= blue) {
        switch (nums[p]) {
            case 0:
                swap(nums, red++, p)
                p++
                break;
            case 1://遇見(jiàn)1 一直讓p++ 這樣即使交換過(guò)來(lái)的是2 也是處于正確的位置
                p++
                break;
            case 2:
                swap(nums, blue--, p)
            
                break;
            default:
                break;
        }
    }
};

java

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

//寫(xiě)法2
public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        int red = 0;
        int blue = len;
        int p = 0;
      
        while (p < blue) {
            if (nums[p] == 0) {
                swap(nums, p, red);
                red++;
                p++;
            } else if (nums[p] == 1) {
                p++;
            } else {
                blue--;
                swap(nums, p, blue);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

167. 兩數(shù)之和 II - 輸入有序數(shù)組 (easy)

ds_122

方法1:二分法

• 思路：循環(huán)數(shù)組，從當(dāng)前元素右邊的元素二分查找另一個(gè)元素，使他們的和是target
• 復(fù)雜度：時(shí)間復(fù)雜度O(nlogn)，遍歷數(shù)組，每次遍歷都進(jìn)行了二分?？臻g復(fù)雜度O(1)

js：

var twoSum = function (numbers, target) {
    let len = numbers.length,
        left = 0,
        right = len - 1,
        mid = 0
    for (let i = 0; i < len; ++i) {//循環(huán)數(shù)組，從右邊的元素二分查找另一個(gè)元素
        left = i + 1
        while (left <= right) {
            mid = parseInt((right - left) / 2) + left
            if (numbers[mid] == target - numbers[i]) {
                return [i + 1, mid + 1]
            } else if (numbers[mid] > target - numbers[i]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
    }
    return [-1, -1]
}

java：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int left = i + 1, right = numbers.length - 1;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
}

方法2:雙指針

• 思路：應(yīng)以left和right指針，初始分別在數(shù)組的兩端，然后不斷判斷兩個(gè)指針指向的數(shù)字之和 和target的大小，和大了 ，right左移一位，和小了，left右移一位
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，數(shù)組總共遍歷一次。空間復(fù)雜度O(1)

js:

var twoSum = function (numbers, target) {
    let [left, right] = [0, numbers.length - 1];//左右指針
    while (left < right) {//
        if (numbers[left] + numbers[right] > target) {//和大了 right左移一位
            right--;
        } else if (numbers[left] + numbers[right] < target) {//和小了left右移一位
            left++;
        } else {
            return [left + 1, right + 1];
        }
    }
};

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                ++left;
            } else {
                --right;
            }
        }
        return new int[]{-1, -1};
    }
}

209. 長(zhǎng)度最小的子數(shù)組 (medium)

方法1:滑動(dòng)窗口

動(dòng)畫(huà)過(guò)大，點(diǎn)擊查看

• 思路：左右指針是滑動(dòng)窗口的兩邊，用滑動(dòng)窗口循環(huán)數(shù)組，不斷擴(kuò)大窗口，如果窗口中元素的和大于target，就開(kāi)始縮小窗口，然后更新最小滑動(dòng)窗口
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，數(shù)組中的元素都遍歷一次，空間復(fù)雜度O(1)

js：

var minSubArrayLen = function(target, nums) {
    const len = nums.length;
    let l = r = sum = 0, 
        res = len + 1; //最大的窗口不會(huì)超過(guò)自身長(zhǎng)度
    while(r < len) {
        sum += nums[r++];//擴(kuò)大窗口
        while(sum >= target) {
            res = res < r - l ? res : r - l;//更新最小值
            sum-=nums[l++];//縮小窗口
        }
    }
    return res > len ? 0 : res;
};

java：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

349. 兩個(gè)數(shù)組的交集 (easy)

方法1：集合

• 思路：先將數(shù)組轉(zhuǎn)成set，然后遍歷長(zhǎng)度小的set，判斷set1中的元素是否存在于set2中，存在的話就是其中一個(gè)交集。
• 復(fù)雜度：時(shí)間復(fù)雜度O(m+n)，m，n是兩數(shù)組的長(zhǎng)度，數(shù)組轉(zhuǎn)成集合的時(shí)間復(fù)雜度就是數(shù)組的長(zhǎng)度，遍歷尋找交集的復(fù)雜度是O(min(m,n))?？臻g復(fù)雜度O(m+n)，就是兩個(gè)set的空間

js：

var intersection = function (nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);//數(shù)組轉(zhuǎn)成set
    if (set1.size > set2.size) {//用size小的數(shù)組遍歷
        [set1, set2] = [set2, set1]
    }
    const intersection = new Set();
    for (const num of set1) {//遍歷set1
        if (set2.has(num)) {//元素如果不存在于set2中就加入intersection
            intersection.add(num);
        }
    }
    return [...intersection];//轉(zhuǎn)成數(shù)組
};

java：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        return getIntersection(set1, set2);
    }

    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        if (set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }
        return intersection;
    }
}

方法2：排序+雙指針

動(dòng)畫(huà)過(guò)大，點(diǎn)擊查看

• 思路：數(shù)組排序，然后用兩個(gè)指針?lè)謩e遍歷數(shù)組，如果兩個(gè)指針指向的元素相等 就是其中一個(gè)交集，否則比較兩個(gè)指針指向的元素的大小，較小的向前移動(dòng)
• 復(fù)雜度：時(shí)間復(fù)雜度O(mlogm+nlogn)，兩數(shù)組快排時(shí)間復(fù)雜度分別是O(mlogm)、O(nlogn)，雙指針遍歷需要O(m+n)，復(fù)雜度取決于較大的O(mlogm+nlogn)?？臻g復(fù)雜度O(logm+logn)排序使用的額外空間

js：

// nums1 = [4,5,9]
// nums2 = [4,4,8,9,9]
// intersection = [4,9]
var intersection = function (nums1, nums2) {
    nums1.sort((x, y) => x - y);//排序
    nums2.sort((x, y) => x - y);
    const length1 = nums1.length,
        length2 = nums2.length;
    let index1 = 0,//雙指針
        index2 = 0;
    const intersection = [];
    while (index1 < length1 && index2 < length2) {//雙指針遍歷數(shù)組
        const num1 = nums1[index1],
            num2 = nums2[index2];
        if (num1 === num2) {//如果兩個(gè)指針指向的元素相等 就時(shí)其中一個(gè)交集
            //防止重復(fù)加入
            if (num1 !== intersection[intersection.length - 1]) {
                intersection.push(num1);
            }
            index1++;
            index2++;
        } else if (num1 < num2) {
            index1++;//num1 < num2說(shuō)明mums1需要向右移動(dòng)
        } else {
            index2++;//num1 > num2說(shuō)明mums1需要向左移動(dòng)
        }
    }
    return intersection;
};

Java；

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

350. 兩個(gè)數(shù)組的交集 II （easy）

方法1:哈希表

• 思路：統(tǒng)計(jì)nums1中各個(gè)元素的頻次，循環(huán)nums2，看nums2中的元素是否在mums1頻數(shù)哈希表中存在，存在的話加入結(jié)果，并且頻數(shù)減1
• 復(fù)雜度：時(shí)間復(fù)雜度O(m+n)，遍歷兩個(gè)數(shù)組，哈希表操作復(fù)雜度是O(1)。空間復(fù)雜度O(min(m,n))對(duì)長(zhǎng)度小的數(shù)組進(jìn)行哈希。

js：

const intersect = (nums1, nums2) => {
    const map = {};
    const res = [];
    if (nums1.length < nums2.length) {
        [nums1, nums2] = [nums2, nums1]
    }
    for (const num1 of nums1) {//nums1中各個(gè)元素的頻次
        if (map[num1]) {
            map[num1]++;
        } else {
            map[num1] = 1;
        }
    }
    for (const num2 of nums2) { //遍歷nums2
        const val = map[num2];
        if (val > 0) {            //在nums1中
            res.push(num2);         //加入res數(shù)組
            map[num2]--;            //匹配掉一個(gè)，就減一個(gè)
        }
    }
    return res;
};

java：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

方法2:雙指針

• 思路：p1，p2雙指針指向兩數(shù)組中的元素，在p1，p2都不越界的情況下開(kāi)始循環(huán)，如果p1指向的元素大，移動(dòng)p2，如果p2指向的元素大，移動(dòng)p1，遇到相同則加入入res，移動(dòng)兩指針
• 復(fù)雜度：時(shí)間復(fù)雜度O(mlogm+nlogn)，m、n分別是數(shù)組的長(zhǎng)度，排序時(shí)間復(fù)雜度是O(mlogm+nlogn)，兩數(shù)組遍歷是O(m+n)?？臻g復(fù)雜度O(logm+logn)

js：

const intersect = (nums1, nums2) => {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b); //排序兩個(gè)數(shù)組
    const res = [];
    let p1 = 0;//指向nums1中的元素
    let p2 = 0;//指向nums2中的元素
    while (p1 < nums1.length && p2 < nums2.length) {//不越界條件
        if (nums1[p1] > nums2[p2]) {//p1指向的元素大，移動(dòng)p2
            p2++;
        } else if (nums1[p1] < nums2[p2]) {//p2指向的元素大，移動(dòng)p1
            p1++;
        } else {
            //遇到相同則加入入res，移動(dòng)兩指針
            res.push(nums1[p1]);
            p1++;
            p2++;
        }
    }
    return res;
};

java：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int p1 = 0, p2 = 0, index = 0;
        while (p1 < length1 && p2 < length2) {
            if (nums1[p1] < nums2[p2]) {
                p1++;
            } else if (nums1[p1] > nums2[p2]) {
                p2++;
            } else {
                intersection[index] = nums1[p1];
                p1++;
                p2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

27. 移除元素 (easy)

• 思路：用雙指針遍歷數(shù)組，left初始化在0號(hào)位置，right初始化在nums.length的位置，當(dāng)left<right的時(shí)候循環(huán)數(shù)組
  1. 當(dāng)nums[left] === val的時(shí)候，用right-1的位置覆蓋left的位置指向的元素，然后向左移動(dòng)right
  2. 當(dāng)nums[left] !== val的時(shí)候，說(shuō)明當(dāng)前元素不需要覆蓋，直接讓left++
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，數(shù)組遍歷一遍。空間復(fù)雜度O(1)

js：

//方法1
//例: [1,2,3,4,5]，  val=1
//    [2,3,4,5,5]，  
var removeElement = function(nums, val) {
    const n = nums.length;
    let left = 0;//left指針初始在0號(hào)位置
    for (let right = 0; right < n; right++) {//用right指針循環(huán)數(shù)組
        if (nums[right] !== val) {//當(dāng)前元素不為val，則直接覆蓋left位置的元素
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
};

//優(yōu)化 題意是可以不考慮數(shù)組元素的順序
//當(dāng)數(shù)組是[1,2,3,4,5]，需要?jiǎng)h除的元素是1的時(shí)候，如果直接刪除，則需要不斷將1之后的元素都向前移動(dòng)一位
//當(dāng)數(shù)組長(zhǎng)度很大的時(shí)候比較消耗性能
//我們我們直接讓right初始化在nums.length的位置 left初始化在0號(hào)位置
//當(dāng)left<right的時(shí)候 循環(huán)數(shù)組
//當(dāng)nums[left] === val的時(shí)候，用right-1的位置覆蓋left的位置指向的元素，然后向左移動(dòng)right
//當(dāng)nums[left] !== val的時(shí)候，說(shuō)明當(dāng)前元素不需要覆蓋，直接讓left++

//例: [1,2,3,4,5]，  val=1
//      [5,2,3,4,5]
var removeElement = function(nums, val) {
    let left = 0, right = nums.length;
    while (left < right) {
        if (nums[left] === val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
};

java：

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

//優(yōu)化
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

217. 存在重復(fù)元素 （easy）

方法1.排序

• 思路：先排序，然后循環(huán)數(shù)組，判斷相鄰元素是否相同
• 復(fù)雜度：時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)，排序需要的?？臻g

js：

var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);//排序
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] === nums[i + 1]) {//判斷相鄰元素是否相同
            return true;
        }
    }
    return false;
};

java：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

方法2.哈希表

• 思路：循環(huán)數(shù)組，將元素存入set，判斷每個(gè)元素是否存在于set中
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

js：

var containsDuplicate = function(nums) {
    const set = new Set();
    for (const x of nums) {
        if (set.has(x)) {
            return true;
        }
        set.add(x);
    }
    return false;
};

java：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

238. 除自身以外數(shù)組的乘積 (medium)

ds_177

• 思路：從左往右遍歷，記錄從左到當(dāng)前位置前一位的乘積，然后從右往左遍歷，從左到當(dāng)前位置前一位的乘積乘上右邊元素的積。
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var productExceptSelf = function (nums) {
    const res = [];
    res[0] = 1;
    //從左往右遍歷
    //記錄從左到當(dāng)前位置前一位的乘積
    for (let i = 1; i < nums.length; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }

    let right = 1;
    //從右往左遍歷
    //從左到當(dāng)前位置前一位的乘積 乘上 右邊元素的積
    for (let j = nums.length - 1; j >= 0; j--) {
        res[j] *= right;
        right *= nums[j];
    }

    return res;
};

java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        res[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i - 1] * nums[i - 1];

        }
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {

            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
}

905. 按奇偶排序數(shù)組 (easy)

方法1.排序

• 思路：排序比較，偶數(shù)在前，奇數(shù)在后
• 復(fù)雜度：時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)，排序額外的空間

js：

var sortArrayByParity = function(A) {
    return A.sort((a, b) => (a & 1) - (b & 1))
};

方法2.雙指針

ds_187

• 思路：右指針從右往左，直到遇到第一個(gè)偶數(shù)，左指針從左往右，直到遇到第一個(gè)奇數(shù)，然后交換位置
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js:

var sortArrayByParity = function(A, l = 0, r = A.length - 1) {
    while(l !== r) {
        while (r > 0 && A[r] & 1) r--
        while (l < r && (A[l] & 1) === 0) l++
        [A[l], A[r]] = [A[r], A[l]]
    }
    return A
};

java：

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int i = 0, j = A.length - 1;
        while (i < j) {
            if (A[i] % 2 > A[j] % 2) {
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }

            if (A[i] % 2 == 0) i++;
            if (A[j] % 2 == 1) j--;
        }

        return A;
    }
}

922. 按奇偶排序數(shù)組 II （easy）

方法1.雙指針

ds_188

• 思路：循環(huán)偶數(shù)位置 如果遇到了奇數(shù)，然后循環(huán)奇數(shù)位置 如果遇到了第一個(gè)偶數(shù)，就交位
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

const swap = (nums, i, j) => {
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
};
var sortArrayByParityII = function(nums) {
    const n  = nums.length;
    let j = 1;
    for (let i = 0; i < n; i += 2) {
        if (nums[i] & 1) {//循環(huán)偶數(shù)位置 如果遇到了奇數(shù)
            while (nums[j] & 1) {//循環(huán)奇數(shù)位置 如果遇到了第一個(gè)偶數(shù)
                j += 2;
            }
            swap(nums, i, j);//交位置換
        }
    }   
    return nums;
};

java：

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int j = 1;
        for (int i = 0; i < n; i += 2) {
            if (nums[i] % 2 == 1) {
                while (nums[j] % 2 == 1) {
                    j += 2;
                }
                swap(nums, i, j);
            }
        }   
        return nums;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}