{"id":38402,"date":"2023-12-11T14:44:21","date_gmt":"2023-12-11T06:44:21","guid":{"rendered":"https:\/\/wx.kaifamiao.info\/?p=38402"},"modified":"2023-12-11T14:44:21","modified_gmt":"2023-12-11T06:44:21","slug":"%e6%89%8b%e5%86%99%e4%bb%a3%e7%a0%81%ef%bc%9a%e6%95%b0%e7%bb%84%e7%9a%842-sum3-sum%e9%97%ae%e9%a2%98%ef%bc%88leetcode%e5%8e%9f%e9%a2%98%ef%bc%89","status":"publish","type":"post","link":"http:\/\/wx.kaifamiao.info\/index.php\/2023\/12\/11\/%e6%89%8b%e5%86%99%e4%bb%a3%e7%a0%81%ef%bc%9a%e6%95%b0%e7%bb%84%e7%9a%842-sum3-sum%e9%97%ae%e9%a2%98%ef%bc%88leetcode%e5%8e%9f%e9%a2%98%ef%bc%89\/","title":{"rendered":"\u624b\u5199\u4ee3\u7801\uff1a\u6570\u7ec4\u76842-sum,3-sum,\u95ee\u9898\uff08leetcode\u539f\u9898\uff09"},"content":{"rendered":"

“`” \u53c2\u8003\u56de\u7b54\uff1a<\/p>\n

2SUM\u95ee\u9898<\/p>\n

\u6700\u5e38\u89c1\u7684\u662f2SUM\u95ee\u9898\uff08<a href=""https:\/\/leetcode.com\/problems\/two-sum\/"">1. 2SUM<\/a>\uff09\uff0c\u5c31\u662f\u6570\u7ec4\u4e2d\u627e\u51fa\u4e24\u4e2a\u6570\u76f8\u52a0\u548c\u4e3a\u7ed9\u5b9a\u7684\u6570\u3002
\n\u8fd9\u9053\u9898\u6709\u4e24\u79cd\u601d\u8def\uff1a <\/p>\n

<ol start="""">
\n<li>\u4e00\u79cd\u601d\u8def\u4ece\u9996\u5c3e\u641c\u7d22\u4e24\u4e2a\u6570\u7684\u548c\uff0c\u5e76\u9010\u6b65\u903c\u8fd1\u3002 <\/li>
\n<li>\u53e6\u5916\u4e00\u79cd\u601d\u8def\u662f\u56fa\u5b9a\u4e00\u4e2a\u6570A\uff0c\u770bSUM-A\u662f\u5426\u5728\u8fd9\u4e2a\u6570\u7ec4\u4e4b\u4e2d\u3002<\/li>
\n<\/ol><\/p>\n

\u5bf9\u4e8e\u7b2c\u4e00\u79cd\u601d\u8def\u5982\u4e0b\uff1a<\/p>\n

\u6b64\u65b9\u6cd5\u662f\u5148\u5c06\u6570\u7ec4\u4ece\u5c0f\u5230\u5927\u6392\u5e8f
\n\u8bbe\u7f6e\u4e24\u4e2a\u6307\u9488\uff0c\u4e00\u4e2a\u6307\u5411\u6570\u7ec4\u5f00\u5934\uff0c\u4e00\u4e2a\u6307\u5411\u6570\u7ec4\u7ed3\u5c3e\uff0c\u4ece\u4e24\u8fb9\u5f80\u4e2d\u95f4\u8d70\u3002\u76f4\u5230\u626b\u5230\u6ee1\u8db3\u9898\u610f\u7684\u4e3a\u6b62\u6216\u8005\u4e24\u4e2a\u6307\u9488\u76f8\u9047\u4e3a\u6b62\u3002
\n\u6b64\u65f6\u8fd9\u79cd\u641c\u7d22\u65b9\u6cd5\u5c31\u662f\u7c7b\u4f3c\u4e8e\u6768\u6c0f\u77e9\u9635\u7684\u641c\u7d22\u65b9\u6cd5\uff0c\u5c31\u662f\u4ece\u6768\u6c0f\u77e9\u9635\u7684\u5de6\u4e0b\u89d2\u5f00\u59cb\u641c\u7d22\uff0c\u76f4\u5230\u627e\u5230\u4e3a\u6b62\u3002
\n\u5982\u679c\u6b64\u65f6\u9898\u76ee\u6761\u4ef6\u53d8\u4e3a\u5982\u679c\u6ca1\u6709\u627e\u51fa\u6700\u63a5\u8fd1\u76842SUM\u548c\u95ee\u9898\uff0c\u89e3\u51b3\u65b9\u6cd5\u8ddf\u4e0a\u9762\u662f\u4e00\u6837\u7684
\n\u7528\u8fd9\u79cd\u65b9\u6cd52SUM\u95ee\u9898\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(nlogn)O(nlog\u2061n)\u7684\uff0c\u4e3b\u8981\u5728\u4e8e\u6392\u5e8f\u7684\u65f6\u95f4\u3002<\/p>\n

\u7b2c\u4e8c\u79cd\u601d\u8def\u65b9\u6cd5\u5982\u4e0b\uff1a<\/p>\n

\u5bf9\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e2a\u6570\u5efa\u7acb\u4e00\u4e2amap\/hash_map \u7136\u540e\u518d\u626b\u4e00\u904d\u8fd9\u4e2a\u6570\u7ec4\uff0c\u5224\u65adtarget-nums[i]\u662f\u5426\u5b58\u5728\uff0c\u5982\u679c\u5b58\u5728\u5219\u8bf4\u660e\u6709\uff0c\u4e0d\u5b58\u5728\u7ee7\u7eed\u627e\u3002\u5f53\u7136\u8fd9\u6837\u505a\u7684\u8bdd\uff0c\u9700\u8981\u5904\u7406\u4e00\u4e2a\u7ec6\u8282\uff1a\u5224\u91cd\u7684\u95ee\u9898\u3002
\n\u4ee3\u7801\u5982\u4e0b\u3010\u6ce8\u610f\u56e0\u4e3a\u9898\u76ee\u4e2d\u8bf4\u4e00\u5b9a\u6709\u89e3\u6240\u4ee5\u624d\u4e0b\u9762\u8fd9\u6837\u5199\uff0c\u5982\u679c\u4e0d\u4e00\u5b9a\u6709\u89e3\uff0c\u5219\u8fd8\u8981\u518d\u52a0\u4e00\u4e9b\u5224\u65ad\u3011<\/p>\n

<pre><code>vector<int> twoSum(vector<int>& nums, int target) {
\nunordered_map<int,vector<int>> mark;
\nfor(int i=0;i<nums.size();i++)
\nmark[nums[i]].push_back(i);
\nfor(int i = 0;i<nums.size();i++){
\nif(target-nums[i] == nums[i]){
\nif(mark[nums[i]].size() > 1){
\nvector<int> tmp{i,mark[nums[i]][1]};
\nreturn tmp;
\n}
\n}else{
\nif(mark.find(target-nums[i]) != mark.end()){
\nvector<int> tmp{i,mark[target-nums[i]][0]};
\nreturn tmp;
\n}
\n}
\n}
\n}
\n<\/code><\/pre><\/p>\n

\u00a0<\/p>\n

3-SUM \u95ee\u9898<\/p>\n

<strong>Question<\/strong>: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.The solution set must not contain duplicate triplets.<\/p>\n

\u6839\u636e\u7ed9\u5b9a\u7684\u5bb9\u91cf\u4e3a n \u7684\u6574\u6570\u6570\u7ec4\uff0c\u627e\u5230\u6240\u6709\u6ee1\u8db3 a + b + c = 0 \u7684\u4e09\u4e2a\u5143\u7d20a\u3001b \u3001c\u7ec4\u5408\uff0c\u9700\u53bb\u91cd\uff1b<\/p>\n

\u89e3\u6cd5<\/p>\n

\u4fee\u6539\u95ee\u9898\u4e3a\uff1a\u6ee1\u8db3 a + b + c = target\uff0ctarget\u662f\u7ed9\u5b9a\u6570\uff0c\u539f\u9898\u5373 target = 0\uff1b<\/p>\n

\u6839\u636e\u9898\u76ee\u53ef\u77e5\uff0c\u4e0e 2-SUM \u95ee\u9898\u7c7b\u4f3c\uff0c\u5728\u6574\u6570\u6570\u7ec4\u4e2d\u4e0d\u653e\u56de\u7684\u53d6\u51fa\u4e09\u4e2a\u5143\u7d20\uff0c\u5176\u548c\u7b49\u4e8e\u7ed9\u5b9a\u6570\uff080\uff09\uff0c\u4e0d\u540c\u7684\u662f\uff0c\u6ee1\u8db3\u6761\u4ef6\u7684\u89e3\u6709\u591a\u4e2a\u800c\u4e14\u9700\u8981\u53bb\u91cd\uff1b<\/p>\n

\u9996\u5148\u60f3\u5230\u7684\u89e3\u6cd5\u662f\uff0c\u904d\u5386\u6570\u7ec4\uff0c\u7136\u540e\u8c03\u7528 2-SUM \u95ee\u9898\u4e2d\u7684\u65b9\u6cd5\u5bfb\u627e\u4e24\u4e2a\u5143\u7d20\u76f8\u52a0\u7b49\u4e8e\u5f53\u524d\u5143\u7d20\u7684\u8865\u8db3\uff0c\u6700\u540e\u6267\u884c\u53bb\u91cd\u64cd\u4f5c\uff1b\u8fd9\u6837\u7684\u8bdd\uff0c\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n^2)<\/span>\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(n^2)<\/span>\uff0c\u53bb\u91cd\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n^2)<\/span>\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(1)<\/span>\uff0c\u8fd9\u7edd\u5bf9\u4e0d\u80fd\u7b97\u4e00\u4e2a\u597d\u65b9\u6848\uff1b<\/p>\n

\u601d\u8003\u5176\u4ed6\u601d\u8def\uff0c\u65e2\u7136\u8981\u53bb\u91cd\uff0c\u53ef\u4ee5\u5148\u5bf9\u6570\u7ec4\u6267\u884c\u4e00\u6b21\u6392\u5e8f\uff0c\u8fd9\u6837\u7684\u8bdd\u5728\u904d\u5386\u7684\u65f6\u5019\u53ef\u4ee5\u8df3\u8fc7\u76f8\u540c\u5143\u7d20\uff1b\u5728\u786e\u5b9a\u4e00\u4e2a\u5f53\u524d\u5143\u7d20\u540e\uff0c\u627e\u53e6\u5916\u4e24\u4e2a\u5143\u7d20\u76f8\u52a0\u4f5c\u4e3a\u5f53\u524d\u5143\u7d20\u7684\u8865\u8db3\uff0c\u6b64\u65f6\u7684\u89e3\u53ef\u80fd\u662f\u591a\u4e2a\u7684\uff0c\u91c7\u7528\u9996\u5c3e\u6807\u8bb0\u7684\u65b9\u5f0f\u53ef\u4ee5\u4e00\u6b21\u904d\u5386\u5b8c\u6210\u67e5\u627e\uff1b<\/p>\n

<pre><code class=""language-java"" lang=""java"">public List<List<Integer>> threeSum(int[] nums, int target){
\n int length = nums.length;
\n List<List<Integer>> result = new ArrayList<>();
\n Arrays.sort(nums);
\n for(int i = 0; i < length – 2; i++) {
\n if(nums[i] + nums[i+1] + nums[i+2] > target)break; \/\/ too large
\n if(nums[i] + nums[length-1] + nums[length-2] < target)continue; \/\/ too small
\n if(i > 0 && nums[i] == nums[i – 1]) continue;
\n int left = i + 1;
\n int right = length – 1;
\n while(left < right){
\n int diff = target – nums[i] – nums[left] – nums[right];
\n if (diff == 0){
\n result.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
\n while(left < right && nums[left] == nums[left + 1]) left++;
\n while(left < right && nums[right] == nums[right – 1]) right–;
\n left++;
\n right–;
\n }else if (diff > 0){
\n left++;
\n }else {
\n right–;
\n }
\n }
\n }
\n return result;
\n}
\n<\/code><\/pre><\/p>\n

\u00a0<\/p>\n

<pre><code> "“`
\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"

“`” \u53c2\u8003\u56de\u7b54\uff1a 2SUM\u95ee\u9898 \u6700\u5e38\u89c1\u7684\u662f2SUM\u95ee\u9898\uff08<a href=&qu […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-38402","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38402","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=38402"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38402\/revisions"}],"predecessor-version":[{"id":38403,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38402\/revisions\/38403"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=38402"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=38402"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=38402"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}