力扣题解(数组)

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

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) 
            return nums.size();
        int j = 0;
        for (int i = 1; i < nums.size(); i++) {
            if(nums[j] != nums[i]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return ++j;
    }
};

面试题 16.21. 交换和

class Solution {
public:
    vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {
        vector<int> res;
        int s1 = 0, s2 = 0;
        for (auto x: array1)
            s1 += x;
        for (auto x: array2)
            s2 += x;
        int d = s2 - s1;
        if (d % 2 != 0) return res;
        int share = d / 2;
        unordered_set<int> a1_set(array1.begin(), array1.end());
        for(auto e2: array2) {
            if (a1_set.count(e2 - share) > 0) {
                res.push_back(e2 - share);
                res.push_back(e2);
                break;
            }
        }
        return res;
    }
};

面试题 17.10. 主要元素

摩尔投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = 0, cnt = 0;
        for (auto num : nums) {
            if (cnt == 0) {
                major = num;
                cnt ++;
            } else {
                if (num == major) {
                    cnt ++;
                } else {
                    cnt --;
                }
            }
        }
        // 验证
        cnt = 0;
        for (auto num: nums) {
            if (num == major) {
                cnt ++;
            }
        }
        if (cnt > nums.size() / 2)
            return major;
        else
            return -1;
    }
};

15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ans;
        if (nums.size() < 3) return ans;
        sort(nums.begin(), nums.end());  // 排序
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0)  // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                break;
            if (i > 0 && nums[i] == nums[i - 1])  // 去重
                continue;
            int L = i + 1;
            int R = nums.size() - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    vector<int> tmp = {nums[i], nums[L], nums[R]};
                    ans.push_back(tmp);
                    while(L < R && nums[L] == nums[L + 1]) L++;  // 去重
                    while(L < R && nums[R] == nums[R - 1]) R--;  // 去重
                    L++;
                    R--;
                } else if (sum < 0) {
                    L++;
                } else if (sum > 0) {
                    R--;
                }
            }
        }
        return ans;
    }
};