C++实现LeetCode(18.四数之和)

[LeetCode] 18. 4Sum 四数之和

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, abcd)
  • The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1,  0, 0, 1)
(-2, -1, 1, 2)
(-2,  0, 0, 2)

LeetCode 中关于数字之和还有其他几道,分别是 Two Sum ,3Sum ,3Sum Closest,虽然难度在递增,但是整体的套路都是一样的,在这里为了避免重复项,我们使用了 STL 中的 TreeSet,其特点是不能有重复,如果新加入的数在 TreeSet 中原本就存在的话,插入操作就会失败,这样能很好的避免的重复项的存在。此题的 O(n^3) 解法的思路跟 3Sum 基本没啥区别,就是多加了一层 for 循环,其他的都一样,代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < int(nums.size() - 3); ++i) {
            for (int j = i + 1; j < int(nums.size() - 2); ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.size() - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        vector<int> out{nums[i], nums[j], nums[left], nums[right]};
                        res.insert(out);
                        ++left; --right;
                    } else if (sum < target) ++left;
                    else --right;
                }
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};

但是毕竟用 TreeSet 来进行去重复的处理还是有些取巧,可能在 Java 中就不能这么做,那么还是来看一种比较正统的做法吧,手动进行去重复处理。主要可以进行的有三个地方,首先在两个 for 循环下可以各放一个,因为一旦当前的数字跟上面处理过的数字相同了,那么找下来肯定还是重复的。之后就是当 sum 等于 target 的时候了,在将四个数字加入结果 res 之后,left 和 right 都需要去重复处理,分别像各自的方面遍历即可,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        vector<int> out{nums[i], nums[j], nums[left], nums[right]};
                        res.push_back(out);
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) --right;
                        ++left; --right;
                    } else if (sum < target) ++left;
                    else --right;
                }
            }
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(18.四数之和)的文章就介绍到这了,更多相关C++实现四数之和内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(769.可排序的最大块数)

    [LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them,

  • C++实现LeetCode(45.跳跃游戏之二)

    [LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i

  • C++实现LeetCode(13.罗马数字转化成整数)

    [LeetCode] 13. Roman to Integer 罗马数字转化成整数 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol       Value I                  1 V                 5 X                10 L                 50 C                100 D 

  • C++实现LeetCode(14.最长共同前缀)

    [LeetCode] 14. Longest Common Prefix 最长共同前缀 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow",&q

  • C++实现LeetCode(12.整数转化成罗马数字)

    [LeetCode] 12. Integer to Roman 整数转化成罗马数字 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol       Value I                   1 V                  5 X                 10 L                  50 C                100

  • C++实现LeetCode(17.电话号码的字母组合)

    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt

  • C++实现LeetCode(55.跳跃游戏)

    [LeetCode] 55. Jump Game 跳跃游戏 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach th

  • C++实现LeetCode(16.最近三数之和)

    [LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on

  • C++实现LeetCode(18.四数之和)

    [LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be

  • Java实现LeetCode(两数之和)

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode(三数之和)

    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode(167.两数之和之二 - 输入数组有序)

    [LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t

  • 关于PHP求解三数之和问题详析

    三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 解题思路

  • JS求解两数之和算法详解

    本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num

  • C++实现LeetCode(29.两数相除)

    [LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate

  • C++实现LeetCode(113.二叉树路径之和之二)

    [LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22,  5 / \ 4   8 /      / \ 11  13  4 /  \         / \ 7  

随机推荐