LeetCode18.四数之和(4sum)——双指针法和回溯法

心已赠人 2022-12-12 02:21 100阅读 0赞

# LeetCode18.四数之和 #

给定一个包含 n 个整数的数组 `nums` 和一个目标值 `target`，判断 `nums` 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 `target` 相等？找出所有满足条件且不重复的四元组。

**注意：**

答案中不可以包含重复的四元组。

**示例：**

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    
    满足要求的四元组集合为：
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

# 双指针法 #

四数之和转三数之和，再转两数之和

class Solution { 
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) { 
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());   //首先排序
            if (nums.empty()) return { };
            
            for(int z = 0; z < nums.size(); z ++){ 
                
                if (z > 0 && nums[z] == nums[z - 1]) continue;
                int newTarget = target - nums[z];   // 将四数之和转化为3数
                
                for(int k = z+1; k < nums.size(); k++){    // 三数变成两数
                    
                    if(k > z+1 && nums[k] == nums[k - 1]) continue;
                    int newTarget2 = newTarget - nums[k];
                    int i = k + 1, j = nums.size() - 1;
                    while (i < j) {               // 两数之和直接套用《两数之和2》的题
                        if (nums[i] + nums[j] == newTarget2) { 
                            res.push_back({ nums[z], nums[k], nums[i], nums[j]});
                            while (i < j && nums[i] == nums[i + 1]) ++i;   //注意去重
                            while (i < j && nums[j] == nums[j - 1]) --j;
                            ++i; --j;
                        } else if (nums[i] + nums[j] < newTarget2) ++i;
                        
                        else --j;
                    }
                }
                
            }
            return res;
            
        }
    };

# 回溯法 #

首先将 nums 升序排序，并把答案四元组中没确定的个数设为 n

我把剪枝分为了 4 类，括号内的是用什么完成剪枝

*  如果剩余可选的数字数量少于 n，则剪掉（递归返回）；
 *  每层递归中，从第二轮循环开始，如果数组中当前数字和前一个相同，则剪掉（进行下一次循环，这条的任务就是去重）；
 *  如果 当前数字 + 已确定数字的和 + (n - 1) \* 排序后数组中当前数字的下一个数字 > target，则说明后面的数无论怎么选，加起来都一定大于 target，所以剪枝（递归返回）；
 *  如果 当前数字 + 已确定数字的和 + (n - 1) \* 排序后数组最后一个数字 < target，则说明当前数字不能选，当前数字加后面的数字都一定小于 target ，所以剪枝（进行下一次循环）；

## cpp版 ##

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution_18_001 { 
    
    private:
    	vector<vector<int>> ans;//结果集
    	vector<int> nums; //排序后的数组
    	vector<int> path; //路径
    	int target;//目标
    	int numSize;//数组长度
    	void dfs(int idx, int sum) { 
    		//满足4个数之和
    		if (sum == target && path.size() == 4) { 
    			ans.emplace_back(path);
    			return;
    		}
    		for (int i = idx; i < numSize; ++i) { 
    			if (numSize - i < int(4 - path.size())) //剪枝
    				return;
    			if (i > idx && nums[i] == nums[i - 1]) //去重
    				continue;
    			if (i < numSize - 1 && (sum + nums[i] + int(3 - path.size()) * nums[i + 1] )> target) //剪枝
    				return;
    			if (i < numSize - 1 && (sum + nums[i] + int(3 - path.size()) * nums[numSize - 1]) < target) //剪枝
    				continue;
    			//添加到路径中
    			path.emplace_back(nums[i]);
    			//深度优先搜索
    			dfs(i + 1, sum + nums[i]);
    			//回溯，从路径中移除
    			path.pop_back();
    		}
    		return;
    	}
    
    public:
    	vector<vector<int>> fourSum(vector<int> &nums, int target) { 
    		sort(nums.begin(), nums.end());
    		this->nums = nums;		//复制一下，不破坏原来的nums
    		this->target = target; //复制一下，不破坏原来的target
    		this->numSize = nums.size();
    		if (numSize < 4)
    			return ans;
    		dfs(0, 0);
    		return ans;
    	}
    };
    
    int main() { 
    
    	//vector初始方案1
    // vector<int> nums; //1, 0, -1, 0, -2, 2
    // nums.push_back(1);
    // nums.push_back(0);
    // nums.push_back(-1);
    // nums.push_back(0);
    // nums.push_back(-2);
    // nums.push_back(2);
    
    	//vector初始方案2
    	int arr[] = { 1, 0, -1, 0, -2, 2};
    	vector<int> nums(arr, arr + sizeof(arr) / sizeof(int));
    
    	//执行四数求和
    	Solution_18_001 s;
    	vector<vector<int>> vvec;
    	vvec = s.fourSum(nums, 0);
    
    	//打印结果
    	vector<vector<int>>::iterator vv = vvec.begin();
    	while (vv != vvec.end()) { 
    		vector<int>::iterator v = (*vv).begin();
    		while (v != (*vv).end()) { 
    			std::cout << *v << "\t";
    			v++;
    		}
    		std::cout << std::endl;
    		vv++;
    	}
    }

## java版 ##

// "static void main" must be defined in a public class.
    
    
    
    public class Main { 
        
        private List<List<Integer>> res;//结果集
        private int target;//目标
    
        public List<List<Integer>> fourSum(int[] nums, int target) { 
            res = new ArrayList<>();
            Arrays.sort(nums);  // 排序便于剪枝操作
            this.target = target;
            helper(nums, 0, 0, new ArrayList<>());
            return res;
        }
    
        private void helper(int[] nums, int index, int target, List<Integer> list) { 
            if (list.size() == 4 && target == this.target) { 
                // 如果数量相等，且和等于target，直接放入结果中
                res.add(new ArrayList<>(list));
                return;
            }
    
            for (int i = index; i < nums.length; i++) { 
                // 后续数量如果已经凑不齐4个，直接剪掉
                if (nums.length - i < 4 - list.size()) return;
                // 避免重复结果
                if (i > index && nums[i] == nums[i - 1]) continue;
                // 这里借鉴了官方题解评论中一位大哥的写法，这样可以精简代码，否则(3 - list.size()) * nums[i + 1]要写成好几个if条件，这样会粗略一些，不过应该还好
                if (i < nums.length - 1 && (target + nums[i] + (3 - list.size()) * nums[i + 1] ) > this.target) return;
                // 这里同上
                if (i < nums.length - 1 && (target + nums[i] + (3 - list.size()) * nums[nums.length - 1] ) < this.target)
                    continue;
                // 下方的代码就是经典的回溯代码了，不再赘述
                list.add(nums[i]);
                helper(nums, i + 1, target + nums[i], list);
                list.remove(list.size() - 1);
            }
        }
        
        public static void main(String[] args) { 
            Main s = new Main();
            int[] nums = { 1, 0, -1, 0, -2, 2};
            List<List<Integer>> list = s.fourSum(nums,0);
            System.out.println(list);
        }
    }

# 参考 #

[leetcode][]  
[leetcode.46.全排列——回溯算法+dfs][leetcode.46._dfs]  
[全排列 ll (Permutations II)——回溯算法+dfs][ll _Permutations II_dfs]  
[emplace\_back() 和 push\_back 的区别][emplace_back_ _ push_back]

[leetcode]: https://leetcode-cn.com/problems/4sum/solution/mei-kan-dao-ji-ge-hui-su-de-ti-jie-na-wo-lai-xie-y/
[leetcode.46._dfs]: https://blog.csdn.net/e891377/article/details/108464715
[ll _Permutations II_dfs]: https://blog.csdn.net/e891377/article/details/108673540
[emplace_back_ _ push_back]: https://blog.csdn.net/xiaolewennofollow/article/details/52559364