1.说明

1.本代码部分注释均来自于ai

2.写完代码可以将代码在脑子里过一遍，可以减少错误率，避免依赖ai修改代码，从而提升自身编码能力。

3.使用C语言建议直接改用c++，具体学习见https://blog.csdn.net/2401_87568987/article/details/153075549?sharetype=blog&shareId=153075549&sharerefer=APP&sharesource=2401_87568987

2.引入

简单移动零

思路：很容易想到我们可以将数组遍历一遍然后将非零的元素移到左边，然后再在后面补零，这便是最简单的双指针。

c/c++：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i=0,n=nums.size();
        for(auto e:nums){
            if(e!=0){
                nums[i]=e;
                i++;
            }
        }
        while(i<n){
            nums[i]=0;
            i++;
        }
    }
};

python：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i=0
        for e in nums:
            if e!=0:
                nums[i]=e
                i+=1
        while(i<len(nums)):
            nums[i]=0
            i+=1
                
        """
        Do not return anything, modify nums in-place instead.
        """

3.三数之和

题目：三数之和

题目分析：

c/c++:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;  // 存储结果
        int n = nums.size();
        sort(nums.begin(), nums.end());  // 排序，为双指针和去重奠基
        
        // 外层循环：固定第一个元素 nums[i]
        for (int i = 0; i < n - 2; ++i) {  // 确保i后至少有2个元素
            // 外层去重：跳过重复的nums[i]
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 剪枝：若当前元素为正，后续均为正，不可能和为0
            if (nums[i] > 0) {
                break;
            }
            
            int l = i + 1;  // 左指针
            int r = n - 1;  // 右指针
            
            // 双指针寻找满足条件的另外两个元素
            while (r > l) {
                int sum_lr = nums[l] + nums[r];
                int target = -nums[i];  // 目标：两数之和需等于 -nums[i]
                
                if (sum_lr < target) {
                    // 和偏小，左指针右移增大总和
                    l++;
                } else if (sum_lr > target) {
                    // 和偏大，右指针左移减小总和
                    r--;
                } else {
                    // 找到有效三元组，加入结果
                    ret.push_back({nums[i], nums[l], nums[r]});
                    
                    // 移动指针并去重（跳过重复元素）
                    r--;
                    l++;
                    // 左指针去重：跳过与前一个元素相同的值
                    while (r > l && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    // 右指针去重：跳过与后一个元素相同的值
                    while (r > l && nums[r] == nums[r + 1]) {
                        r--;
                    }
                }
            }
        }
        return ret;
    }
};

python:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []  # 存储最终结果的列表（三元组的三元组）
        n = len(nums)  # 获取输入数组的长度
        nums.sort()  # 对数组排序：为双指针和去重提供基础（排序后相同元素相邻）
        
        # 外层循环：固定三元组的第一个元素 nums[i]
        # 循环范围是 0 到 n-3（确保 i 之后至少有 2 个元素，即 l 和 r）
        for i in range(0, n - 2):
            # 外层去重：若当前元素与前一个元素相同，跳过（避免重复三元组）
            # i > 0 是为了防止 i=0 时访问 nums[-1] 越界
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # 剪枝优化：若当前元素大于 0，由于数组已排序，后续元素均为正数
            # 三个正数之和不可能为 0，直接终止循环
            if nums[i] > 0:
                break
            
            l = i + 1  # 左指针：从 i 的下一个元素开始（避免重复使用同一元素）
            r = n - 1  # 右指针：从数组末尾开始
            
            # 双指针遍历：寻找与 nums[i] 组成和为 0 的另外两个元素
            while r > l:  # 确保右指针在左指针右侧（有效范围）
                # 计算左右指针元素之和，与目标值（-nums[i]）比较
                if nums[l] + nums[r] < -nums[i]:
                    # 两数之和偏小，需增大总和 → 左指针右移（数组递增，右移后值更大）
                    l += 1
                elif nums[l] + nums[r] > -nums[i]:
                    # 两数之和偏大，需减小总和 → 右指针左移（左移后值更小）
                    r -= 1
                else:
                    # 找到有效三元组（三数之和为 0），添加到结果列表
                    ret.append([nums[i], nums[l], nums[r]])
                    
                    # 移动双指针，继续寻找新的组合（避免重复处理同一对元素）
                    r -= 1
                    l += 1
                    
                    # 内层去重：跳过左指针的重复元素（与上一个元素相同则右移）
                    # 需保证 r > l 避免越界
                    while r > l and nums[l] == nums[l - 1]:
                        l += 1
                    # 内层去重：跳过右指针的重复元素（与下一个元素相同则左移）
                    # 需保证 r > l 避免越界
                    while r > l and nums[r] == nums[r + 1]:
                        r -= 1
        
        return ret  # 返回所有不重复的三元组

练习：四数之和