草庐IT

【leetcode】18. 四数之和

daheww 2023-03-28 原文

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

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

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

题目链接：18. 四数之和

解答

解答四数之和和解答三数之和的思路是一样的。
三数之和的暴力解法是三层for循环，然后使用双指针将两层for循环变成一层。所以三数之和的双指针解法时间复杂度是O(n^2)。
四数之和的暴力解法是四层for循环，然后使用双指针将两层for循环变成一层。所以四数之和的双指针解法的时间复杂度是O(n^3)。

三数之和解答：【leetcode】 15. 三数之和


   public List<List<Integer>> fourSum(int[] nums, int target) {
       List<List<Integer>> result = new ArrayList<>();
       if (nums.length < 4) {
           return result;
       }

       Arrays.sort(nums);
       for (int i = 0; i < nums.length - 3; i++) {
           // 去重1
           if (i != 0 && nums[i - 1] == nums[i]) {
               continue;
           }

           for (int j = i + 1; j < nums.length - 2; j++) {
               // 去重2
               if (j != i + 1 && nums[j - 1] == nums[j]) {
                   continue;
               }

               int left = j + 1;
               int right = nums.length - 1;

               while (left < right) {
                   int sum = nums[i] + nums[j] + nums[left] + nums[right];

                   if (sum == target) {
                       List<Integer> list = new ArrayList<>();
                       list.add(nums[i]);
                       list.add(nums[j]);
                       list.add(nums[left]);
                       list.add(nums[right]);
                       result.add(list);

                       // 去重3
                       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 result;
   }
之和leetcodenumsright算法与数据结构

有关【leetcode】18. 四数之和的更多相关文章

  1. ruby - i18n Assets 管理/翻译 UI - 2

    我正在使用i18n从头开始​​构建一个多语言网络应用程序，虽然我自己可以处理一大堆yml文件，但我说的语言(非常)有限，最终我想寻求外部帮助帮助。我想知道这里是否有人在使用UI插件/gem(与django上的django-rosetta不同)来处理多个翻译器，其中一些翻译器不愿意或无法处理存储库中的100多个文件，处理语言数据。谢谢&问候，安德拉斯(如果您已经在ruby​​onrails-talk上遇到了这个问题，我们深表歉意) 最佳答案 有一个rails3branchofthetolkgem在github上。您可以通过在Gemfi

  2. ruby-on-rails - Rails 3 I18 : translation missing: da. datetime.distance_in_words.about_x_hours - 2

    我看到这个错误:translationmissing:da.datetime.distance_in_words.about_x_hours我的语言环境文件:http://pastie.org/2944890我的看法:我已将其添加到我的application.rb中:config.i18n.load_path+=Dir[Rails.root.join('my','locales','*.{rb,yml}').to_s]config.i18n.default_locale=:da如果我删除I18配置，帮助程序会处理英语。更新:我在config/enviorments/devolpment

  3. ruby-on-rails - 如果我将 ruby​​ 版本 2.5.1 与 rails 版本 2.3.18 一起使用会怎样？ - 2

    如果我使用ruby​​版本2.5.1和Rails版本2.3.18会怎样？我有基于rails2.3.18和ruby​​1.9.2p320构建的rails应用程序，我只想升级ruby的版本，而不是rails，这可能吗？我必须面对哪些挑战？ 最佳答案 GitHub维护apublicfork它有针对旧Rails版本的分支，有各种变化，它们一直在运行。有一段时间，他们在较新的Ruby版本上运行较旧的Rails版本，而不是最初支持的版本，因此您可能会发现一些关于需要向后移植的有用提示。不过，他们现在已经有几年没有使用2.3了，所以充其量只能让更

  4. ruby-on-rails - Ruby on Rails I18n 插值 - 2

    大家好!我对我的:username字段进行了一个小的验证，它应该是4到30个字符。我写了一个验证::length=>{:within=>4..30,:message=>I18n.t('activerecord.errors.range')-我想显示一个错误各种错误的消息(不像，太长或太短)，但这里有一个问题-我可以将最小值和最大值都传递给翻译，以便有类似的东西:用户名应该在4到30个字符之间。目前我有:range:"shouldbebetween%{count}and%{count}characters"，这显然不起作用(只是为了检查)。是否可以从范围中获取这些值？谢谢大家的指教!

  5. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  6. ruby-on-rails - 如果特定语言环境中缺少翻译，如何配置 i18n 以使用 en 语言环境？ - 2

    如果特定语言环境中缺少翻译，如何配置i18n以使用en语言环境翻译？当前已插入翻译缺失消息。我正在使用RoR3.1。 最佳答案 找到相似的question这里是答案:#application.rb#railswillfallbacktoconfig.i18n.default_localetranslationconfig.i18n.fallbacks=true#railswillfallbacktoen,nomatterwhatissetasconfig.i18n.default_localeconfig.i18n.fallback

  7. ruby-on-rails - i18n 与枚举 gem - 2

    我正在使用Enumerizegemhttps://github.com/brainspec/enumerize/它允许我以简单的形式使用漂亮的选择。并且此选择中的所有选项均已翻译。en:enumerize:user:sex:male:'Man'female:'Woman'所以，在我的表单中，我选择了变体“男人”和“女人”。当我用“男人”值保存记录时，我得到了“男性”值的性别属性。现在我想在显示页面上将该值显示为“Man”，但是=@user.sex输出为'male'而不是'Man' 最佳答案 我可能会使用.text方法(您可以通过使用

  8. iNFTnews | 周杰伦18年前未发布的作品Demo，藏在了区块链技术里 - 2

    当音乐碰上区块链技术，会擦出怎样的火花？或许周杰伦已经给了我们答案。8月29日下午，B站独家首发周杰伦限定珍藏Demo独家访谈VCR，周杰伦在VCR里分享了《晴天》《青花瓷》《搁浅》《爱在西元前》四首经典歌曲Demo背后的创作故事，并首次公布18年前未发布的神秘作品《纽约地铁》的Demo。在VCR中，方文山和杰威尔音乐提及到“多亏了区块链技术，现在我们可以将这些Demos，变成独一无二具有收藏价值的艺术品，这些Demos可以在薄盒（国内数藏平台）上听到。”如何将音乐与区块链技术相结合，薄盒方面称：“薄盒作为区块链技术服务方，打破传统对于区块链技术只能作为数字收藏的理解。聚焦于区块链技术赋能，在

  9. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  10. ruby-on-rails - 具有管理 namespace 的 Rails 3 中的 I18n - 2

    我正在根据Rails指南的建议开发Rails应用程序，以创建包含翻译的文件夹树和文件。我的文件夹树与此类似:|-defaults|---es.rb|---en.rb|-models|---book|-----es.rb|-----en.rb|-views|---defaults|-----es.rb|-----en.rb|---books|-----es.rb|-----en.rb|---users|-----es.rb|-----en.rb|---navigation|-----es.rb|-----en.rbconfig/locales/views/books/en.yml中的内容

随机推荐