LeetCode 18. 四数之和 - Rust 实现思路分析使用排序 双指针的方法将四数之和转化为三数之和 一个固定数。时间复杂度: O(n³)空间复杂度: O(1) (不计输出)代码实现implSolution{pubfnfour_sum(mutnums:Veci32,target:i32)-VecVeci32{letmutresult:VecVeci32Vec::new();letnnums.len();ifn4{returnresult;}// 排序nums.sort();foriin0..n-3{// 跳过重复的第一个数ifi0nums[i]nums[i-1]{continue;}// 剪枝最小值已经大于targetif(nums[i]asi64)(nums[i1]asi64)(nums[i2]asi64)(nums[i3]asi64)targetasi64{break;}// 剪枝最大值已经小于targetif(nums[i]asi64)(nums[n-3]asi64)(nums[n-2]asi64)(nums[n-1]asi64)targetasi64{continue;}forjini1..n-2{// 跳过重复的第二个数ifji1nums[j]nums[j-1]{continue;}// 剪枝最小值已经大于targetif(nums[i]asi64)(nums[j]asi64)(nums[j1]asi64)(nums[j2]asi64)targetasi64{break;}// 剪枝最大值已经小于targetif(nums[i]asi64)(nums[j]asi64)(nums[n-2]asi64)(nums[n-1]asi64)targetasi64{continue;}// 双指针letmutleftj1;letmutrightn-1;whileleftright{letsum(nums[i]asi64)(nums[j]asi64)(nums[left]asi64)(nums[right]asi64);ifsumtargetasi64{result.push(vec![nums[i],nums[j],nums[left],nums[right]]);// 跳过重复的左指针whileleftrightnums[left]nums[left1]{left1;}// 跳过重复的右指针whileleftrightnums[right]nums[right-1]{right-1;}left1;right-1;}elseifsumtargetasi64{left1;}else{right-1;}}}}result}}测试用例fnmain(){letnums1vec![1,0,-1,0,-2,2];lettarget10;println!({:?},Solution::four_sum(nums1,target1));// 输出: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]letnums2vec![2,2,2,2,2];lettarget28;println!({:?},Solution::four_sum(nums2,target2));// 输出: [[2,2,2,2]]}算法流程图排序 nums │ ├── 固定第一个数 i (跳过重复) │ │ │ ├── 剪枝判断 │ │ │ ├── 固定第二个数 j (跳过重复) │ │ │ │ │ ├── 剪枝判断 │ │ │ │ │ └── 双指针 left/right 找剩余两数 │ │ ├── sum target → 记录结果去重双指针移动 │ │ ├── sum target → left │ │ └── sum target → right--关键优化点优化说明排序便于去重和双指针跳过重复元素i 0 nums[i] nums[i-1]等剪枝用i64避免溢出提前终止不可能的循环双指针O(n²) 替代暴力 O(n³) 枚举LeetCode 18. 四数之和 - Rust 实现思路分析使用排序 双指针的方法将四数之和转化为三数之和 一个固定数。时间复杂度: O(n³)空间复杂度: O(1) (不计输出)代码实现implSolution{pubfnfour_sum(mutnums:Veci32,target:i32)-VecVeci32{letmutresult:VecVeci32Vec::new();letnnums.len();ifn4{returnresult;}// 排序nums.sort();foriin0..n-3{// 跳过重复的第一个数ifi0nums[i]nums[i-1]{continue;}// 剪枝最小值已经大于targetif(nums[i]asi64)(nums[i1]asi64)(nums[i2]asi64)(nums[i3]asi64)targetasi64{break;}// 剪枝最大值已经小于targetif(nums[i]asi64)(nums[n-3]asi64)(nums[n-2]asi64)(nums[n-1]asi64)targetasi64{continue;}forjini1..n-2{// 跳过重复的第二个数ifji1nums[j]nums[j-1]{continue;}// 剪枝最小值已经大于targetif(nums[i]asi64)(nums[j]asi64)(nums[j1]asi64)(nums[j2]asi64)targetasi64{break;}// 剪枝最大值已经小于targetif(nums[i]asi64)(nums[j]asi64)(nums[n-2]asi64)(nums[n-1]asi64)targetasi64{continue;}// 双指针letmutleftj1;letmutrightn-1;whileleftright{letsum(nums[i]asi64)(nums[j]asi64)(nums[left]asi64)(nums[right]asi64);ifsumtargetasi64{result.push(vec![nums[i],nums[j],nums[left],nums[right]]);// 跳过重复的左指针whileleftrightnums[left]nums[left1]{left1;}// 跳过重复的右指针whileleftrightnums[right]nums[right-1]{right-1;}left1;right-1;}elseifsumtargetasi64{left1;}else{right-1;}}}}result}}测试用例fnmain(){letnums1vec![1,0,-1,0,-2,2];lettarget10;println!({:?},Solution::four_sum(nums1,target1));// 输出: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]letnums2vec![2,2,2,2,2];lettarget28;println!({:?},Solution::four_sum(nums2,target2));// 输出: [[2,2,2,2]]}算法流程图排序 nums │ ├── 固定第一个数 i (跳过重复) │ │ │ ├── 剪枝判断 │ │ │ ├── 固定第二个数 j (跳过重复) │ │ │ │ │ ├── 剪枝判断 │ │ │ │ │ └── 双指针 left/right 找剩余两数 │ │ ├── sum target → 记录结果去重双指针移动 │ │ ├── sum target → left │ │ └── sum target → right--关键优化点优化说明排序便于去重和双指针跳过重复元素i 0 nums[i] nums[i-1]等剪枝用i64避免溢出提前终止不可能的循环双指针O(n²) 替代暴力 O(n³) 枚举