哈希/求和-三数求和

闲狗题库 2023-03-28 原文

题目 LeetCode15
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解题思路
思路1：暴力求解，3 层循环。时间复杂度 O(nnn)
思路2：2 层循环，第 1 层循环遍历数组，作为 target，第二层循环参考两数求和的逻辑。

    // 待优化的代码
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> finalList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
           int target = -nums[i];
            Set<Integer> tempSet = new HashSet<>();
            List<Integer> tempList = new ArrayList<>();
            // 遍历数组 nums
            for (int j = 0; j < nums.length; j++) {
                if(j == i){
                    continue;
                }
                // 每个值都判断 tempSet 中是否存在 target-nums[i]
                if (tempSet.contains(target - nums[j])) {
                    tempList.add(nums[j]);
                    tempList.add(target - nums[j]);
                    tempList.add(nums[i]);
                    boolean flag = true;
                    // 判断 finalList 是否包含 tempList
                    for (List<Integer> list : finalList) {
                        if(tempList.containsAll(list) && list.containsAll(tempList)){
                            flag = false;
                            break;
                        }
                    }
                    if(flag){
                        finalList.add(tempList);
                    }
                    tempList = new ArrayList<>();
                }else{
                    // 如果不存在则将当前的 nums[i]存入 tempList 中，继续遍历直到找到为止
                    tempSet.add(nums[j]);
                }
            }
        }
        return finalList;
    }

思路3：先排序后查找，时间复杂度 O(n*n)

79467cc6d1844a55b65e5912320650b5.jpeg

class Solution {
        public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return list;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 则说明该数字重复，会导致结果重复，所以应该跳过
            int L = i+1;//指针从第二个数开始移动
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    list.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 则会导致结果重复，应该跳过
                    while (L<R && nums[R] == nums[R-1]) R--; // 则会导致结果重复，应该跳过
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return list;
    }
}

求和哈希 nums tempList lt

有关哈希/求和-三数求和的更多相关文章

ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat
ruby - 如何在 Grape 中定义哈希数组？ - 2
我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>
ruby - 在哈希的键数组中追加元素 - 2
查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？最佳答案如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用
ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2
假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解
ruby-on-rails - 使用作为方法的值在 ruby 中搜索哈希 - 2
我在搜索我的值是方法的散列时遇到问题。我只是不想运行plan_type与键匹配的方法。defmethod(plan_type,plan,user){foo:plan_is_foo(plan,user),bar:plan_is_bar(plan,user),waa:plan_is_waa(plan,user),har:plan_is_har(user)}[plan_type]end目前如果我传入“bar”作为plan_type，所有方法都会运行，我怎么能只运行plan_is_bar方法呢？最佳答案这个变体怎么样？defmethod
键删除后 ruby 哈希内存泄漏 - 2
你好，我无法成功如何在散列中删除key后释放内存。当我从哈希中删除键时，内存不会释放，也不会在手动调用GC.start后释放。当从Hash中删除键并且这些对象在某处泄漏时，这是预期的行为还是GC不释放内存？如何在Ruby中删除Hash中的键并在内存中取消分配它？例子:irb(main):001:0>`ps-orss=-p#{Process.pid}`.to_i=>4748irb(main):002:0>a={}=>{}irb(main):003:0>1000000.times{|i|a[i]="test#{i}"}=>1000000irb(main):004:0>`ps-orss=-p
Ruby 哈希直接访问与合并 - 2
有什么区别:@attr[:field]=new_value和@attr.merge(:field=>new_value) 最佳答案如果您使用的是merge!而不是merge，则没有区别。唯一的区别是您可以在合并参数中使用多个字段(意思是:另一个散列)。例子:h1={"a"=>100,"b"=>200}h2={"b"=>254,"c"=>300}h3=h1.merge(h2)putsh1#=>{"a"=>100,"b"=>200}putsh3#=>{"a"=>100,"b"=>254,"c"=>300}h1.merge!(h2)pu
ruby - 如何在 Ruby 中获取多维哈希中的键？ - 2
因此，对于普通哈希，您可以使用它来获取key:hash.keys如何获取如下所示的多维哈希的第二维键:{""=>{"first_name"=>"test","last_name"=>"test_l","username"=>"test_user","title"=>"SalesManager","office"=>"test","email"=>"test@test.com"}}每个项目都是唯一的。所以我想从上面得到的键是:first_name,last_name,username,title,officeandemail 最佳答案
arrays - Ruby:尝试在哈希数组上获取 Enumerator 时，nil:NilClass 的未定义方法 `[]' - 2
我正在尝试循环哈希数组。当我到达获取枚举器开始循环的位置时，出现以下错误:undefinedmethod`[]'fornil:NilClass我的代码如下所示:defextraireAttributs(attributsParam)classeTrouvee=falsescanTrouve=falseownerOSTrouve=falseownerAppTrouve=falseresultat=Hash.new(0)attributs=Array(attributsParam)attributs.eachdo|attribut|#CRASHESHERE!!!typeAttribut=a
ruby - 需要重构为新的 Ruby 1.9 哈希语法 - 2
这个问题在这里已经有了答案:HashsyntaxinRuby[duplicate](1个回答)关闭5年前。我有一个Recipe，其中包含以下未通过lint测试的代码:service'apache'dosupports:status=>true,:restart=>true,:reload=>trueend失败并出现错误:UsethenewRuby1.9hashsyntax.supports:status=>true,:restart=>true,:reload=>true不确定新语法是什么样的...有人可以帮忙吗？

哈希/求和-三数求和

有关哈希/求和-三数求和的更多相关文章

随机推荐