1 四数之和

分析

与三数之和的方法类似

由于与三数之和很类似故此处不写😎

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # 对数组进行排序O(log(n))
        result = []
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i-1]: continue  # 保证不再遍历之前的值
            for j in range(i + 1, len(nums) - 2):
                if j > i + 1 and nums[j] == nums[j-1]: continue  # 保证不在遍历之前的值
                k = j + 1
                m = len(nums) - 1
                while k < m:
                    if nums[i] + nums[j] + nums[k] + nums[m] < target:
                        k += 1
                        while nums[k] == nums[k-1] and k < m: k += 1
                    elif nums[i] + nums[j] + nums[k] + nums[m] > target:
                        m -= 1
                        while nums[m] == nums[m+1] and k < m: m -= 1
                    else:
                        result.append([nums[i], nums[j], nums[k], nums[m]])
                        k += 1
                        m -= 1
                        while nums[k] == nums[k-1] and nums[m] == nums[m+1] and k < m: k += 1
        return result

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        for (auto i = nums.begin(); i < last - 3; i++){
            if (i > nums.begin() && *i == *(i-1)) continue;
            if ((long) *i + *(i + 1) + *(i + 2) + *(i + 3) > target) break;  // 最小的三个数都没target大的话这个数组就不会有了
            if ((long) *i + *(last - 1) + *(last - 2) + *(last - 3) < target) continue;  // 目前跌迭代值和最大的三个数都没有target大的话此次迭代就不会有了
            for (auto j = i + 1; j < last - 2; j++){
                if (j > i + 1 && *j == *(j-1)) continue;
                if ((long) *i + *j + *(j + 1) + *(j + 2) > target) break;
                if ((long) *i + *j + *(last - 1) + *(last - 2) < target) continue;
                auto k = j + 1;
                auto m = nums.end() - 1;
                while (k < m){
                    if ((long) *i + *j + *k + *m < target){
                        k++;
                        while (*k == *(k - 1) && k < m) k++;
                    }
                    else if ((long) *i + *j + *k + *m > target){
                        m--;
                        while (*m == *(m + 1) && k < m) m--;
                    }
                    else{
                        result.push_back({*i, *j, *k, *m});
                        k++;
                        m--;
                        while (*k == *(k - 1) && *m == *(m + 1) && k < m) k++;
                    }
                }
            }
        }
        return result;
    }
};

2 移除元素

分析

只要是原地就可以想想双指针，思路类似Day1的

简单，😎

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[index] = nums[i]
                index += 1
        return index

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;
        auto last = nums.end();
        for (auto i = nums.begin(); i < last; i++){
            if (*i != val) nums[index++] = *i;
        }
        return index;
    }
};

3 下一个排列

分析-灵茶山艾府

排列 [1,3,5,4,2] 的下一个排列是什么？

如果 1,3,5 保持不变，只重新排列 4,2，得到 2,4。排列变小了，这不行。
如果 1,3 保持不变，只重新排列 5,4,2，由于 5 右边都是小于 5 的数，所以重排后，5 这个位置上的数必然变小，导致排列变小，这也不行。
如果 1 保持不变，只重新排列 3,5,4,2，这是可以的，因为 3 右边有比 3 大的数，重排后可以让 3 这个位置上的数变大，从而得到更大的排列。
由于要求的是下一个排列，所以 3 这个位置上的数只要「大一点点」就好了。找到 3 右边最小的大于 3 的数，也就是 4，放到 3 这个位置上。于是，下一个排列是 [1,4,,,_]。
剩余的三个数是 2,3,5。由于只看前两位 [1,4,,,_] 就已经比 [1,3,5,4,2] 大了，所以后三位填最小的排列就行，即按照 2,3,5 的顺序填，得到 [1,4,2,3,5]。

Python
C++

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        a = []; b=[]
        for i in range(len(nums)-2, -1, -1):
            # 找a
            if nums[i] < nums[i + 1]:
                a = a + [i, nums[i]]
                break
        if a:      
            for i in range(len(nums)-1, a[0], -1):
                # 找b
                if nums[i] > a[1]:
                    b = b + [i, nums[i]]
                    break
            nums[a[0]] = b[1]
            nums[b[0]] = a[1]
            nums[a[0]+1:] = sorted(nums[a[0] + 1:])
        else:
            nums.sort()

class Solution {
public:
   void nextPermutation(vector<int>& nums) {
        nextPermutation(nums.begin(), nums.end());
   }

    // 模板函数BidIt用于占位如vector，list等可双向跌打的
    template<typename BidiIt>
    bool nextPermutation(BidiIt first, BidiIt last) {
        const auto rfirst = reverse_iterator<BidiIt>(last);  // 创建反向迭代器
        const auto rlast = reverse_iterator<BidiIt>(first);

        auto pivot = next(rfirst);
        while (pivot != rlast && *pivot >= *prev(pivot)) ++pivot;
        if (pivot == rlast) {
            reverse(rfirst, rlast);
            return false;
        }  // 当数组本身以全部逆序，则下一个排列只需逆序即可

        auto change = find_if(rfirst, pivot, [&pivot](const auto& elem) {
            return elem > *pivot;});  // lambda函数,find_if函数用于指定搜索范围和搜索条件
        swap(*change, *pivot);
        reverse(rfirst, pivot);
        return true;
    }

};