`
cozilla
  • 浏览: 93873 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[LeetCode] 4sum

 
阅读更多

 

 

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
         sort(num.begin(),num.end());
         vector<vector<int> > res;
         int* a = &num[0];
         int len = num.size();
         for (int i = 0; i < len; i++) {
             if (i > 0 && num[i] == num[i-1]) continue;
             for (int j = i+1; j < len; j++) {
                 if (j > i+1 && num[j] == num[j-1]) continue;
                 int x = j+1, y = len - 1;
                 while (x < y) {
                     int t = a[i] + a[j] + a[x] + a[y];
                     if (t == target) {
                         res.push_back({a[i], a[j], a[x], a[y]});
                         while (x < y && a[x+1] == a[x]) x++;
                         while (x < y && a[y-1] == a[y]) y--;
                         x++; y--;
                     } else if (t > target) {
                         y--;
                     } else {
                         x++;
                     }
                 }
             }
         }
         return res;
    }
};

 

 

@2013-10-07

N3

写了个复杂版本的。好处是方便拓展sum(a1...ai)都可以。i=2,3,4,5...

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > res;
        int n = num.size();
        if (n < 4) return res;
        sort(num.begin(), num.end());
        vector<int> v;
        gen(num, res, v, target, 0, 4);
        return res;
    }
    
    void gen(const vector<int>& a,vector<vector<int> >&res, vector<int>& v, int tar, int cur, int total) {
        if (v.size() == total) return;
        if (total - v.size() == 2) {
            int i = cur, j = a.size() - 1;
            while (i < j) {
                if (a[i] + a[j] == tar) {
                    v.push_back(a[i]);
                    v.push_back(a[j]);
                    res.push_back(v);
                    v.pop_back();
                    v.pop_back();
                    int t = i;
                    while (i < j && a[i] == a[t]) i++;
                    t = j;
                    while (i < j && a[j] == a[t]) j--;
                }
                else if (a[i] + a[j] > tar) j--;
                else i++;
            }
            return;
        }
        int prev, i = cur;
        while (i + 3 - v.size() < a.size()) {
            v.push_back(a[i]);
            gen(a, res, v, tar - a[i], i+1, total);
            v.pop_back();
            prev = i;
            while (i < a.size() && a[prev] == a[i]) i++;
        }
    }
};

 

 

分享到:
评论

相关推荐

    Leetcode two sum java 解法

    Leetcode two sum java 解法

    文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码

    本文档主要介绍了在Python编程语言中如何运用双指针算法解决LeetCode上的2Sum、3Sum及4Sum求和问题,并提供了相应的代码实现。LeetCode是一个非常受欢迎的在线编程平台,用于练习算法题目,尤其适合准备技术面试的...

    python数组双指针算法求和问题LeetCode2sum3sum4sum含代码

    本文将深入探讨如何使用Python实现双指针算法来解决LeetCode中的2sum、3sum和4sum问题,并提供相关代码示例。 首先,我们来看2sum问题。给定一个整数数组`nums`和一个目标值`target`,我们需要找到数组中两个数的...

    oj.leetcode 2sum 解

    oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)

    leetcode2sum-leetCodeSolutions:我对leetCode问题的解决方案

    leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...

    leetcode2sum-Problems:编程问题的回购

    LC4: Longest Palindromic Substring [Medium] LC5: Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer [Easy] LC8: String To Integer Atoi [Medium] LC9: Palindrome ...

    2sumleetcode-2SUM:使用先前地图的最快二和O(N)

    leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta khởi...

    leetcode3sum-LeetCode:leetcode问题用C#解决

    3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...

    leetcode3sum-leetcode-curation-topical:技术面试准备清单

    3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...

    leetcode2sum-Q1.-2Sum:力码研究1

    "2Sum"是LeetCode中的一个经典问题,编号为Q1,属于基础级别的算法题。本文将深入探讨这个问题,理解其背后的逻辑,并从中学习到如何有效地解决此类问题。 2Sum问题的核心在于,给定一个整数数组`nums`和一个目标值...

    LeetCode 刷题汇总1

    * 4Sum(4Sum):找到数组中四个元素的和等于目标值的元素。 这些知识点涵盖了算法设计、数据结构、数学运算、字符串操作、链表操作、栈和队列操作、字符串匹配和排序搜索等多方面的内容,为LeetCode刷题提供了一...

    js-leetcode题解之18-4sum.js

    在JavaScript中解决LeetCode的“18-4sum”问题是一个经典的算法挑战,主要任务是编写一个函数来找出所有不同的四个数的组合,这些数的和等于一个给定的目标值。这个问题是著名的“k-sum”问题的一个特例,在算法和...

    2sumleetcode-LeetCode:力码

    leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...

    c语言-leetcode 0001-two-sum.zip

    c c语言_leetcode 0001_two_sum

    java-leetcode题解之Combination Sum.java

    Java实现LeetCode题解之 Combination Sum Java代码示例和详解 在数据结构与算法的学习过程中,组合求和问题是一项基础且常见的问题。LeetCode中的Combination Sum问题正是一个考察回溯法的经典题目。这个问题的目标...

    leetcode3sumnlogn-learn-algorithm:学习算法

    leetcode 3sum nlogn 让我们研究算法 微电脑网 : 2018.09.06。 用 BFS 搜索,用 DP 解决。 我过去没能做到,但感觉很好。 : 2018.09.06。 起初,它以这样的方式重复,如果有什么变化,它会再次旋转。 -&gt; 超时 接下来...

    java-leetcode题解之Combination Sum II.java

    LeetCode上的题目设计旨在帮助程序员提升算法和数据结构的应用能力,而Combination Sum II题解的编写则是检验和加强这些技能的一个途径。因此,掌握这道题的Java解法,对于想要在求职面试中表现出色的程序员来说,是...

    c语言-leetcode 0018-four-sum.zip

    c c语言_leetcode 0018_four_sum.zip

    c语言-leetcode 0015-three-sum.zip

    c c语言_leetcode 0015_three_sum.zip

    LeetCode最全代码

    18| [4 Sum](https://leetcode.com/problems/4sum/) | [C++](./C++/4sum.cpp) [Python](./Python/4sum.py) | _O(n^3)_ | _O(1)_ | Medium || Two Pointers 26 | [Remove Duplicates from Sorted Array]...

Global site tag (gtag.js) - Google Analytics