{"id":2717,"date":"2022-04-13T00:03:09","date_gmt":"2022-04-12T16:03:09","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2717"},"modified":"2022-04-13T17:13:03","modified_gmt":"2022-04-13T09:13:03","slug":"%e7%ae%97%e6%b3%95%e5%9f%ba%e7%a1%80%e7%ac%ac%e4%b8%89%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2717","title":{"rendered":"\u7b97\u6cd5\u57fa\u7840\u7b2c\u4e09\u5929"},"content":{"rendered":"\n

82. \u5220\u9664\u6392\u5e8f\u94fe\u8868\u4e2d\u7684\u91cd\u590d\u5143\u7d20 II<\/a><\/p>\n\n\n\n

\u94fe\u8868\u76f8\u5173\u7684\u9898\u76ee\uff0c\u6211\u662f\u771f\u4e0d\u4f1a\u3002\u3002<\/p>\n\n\n\n

\/**\n<\/em> 82. \u5220\u9664\u6392\u5e8f\u94fe\u8868\u4e2d\u7684\u91cd\u590d\u5143\u7d20 II\n<\/em> \u7ed9\u5b9a\u4e00\u4e2a\u5df2\u6392\u5e8f\u7684\u94fe\u8868\u7684\u5934 head \uff0c \u5220\u9664\u539f\u59cb\u94fe\u8868\u4e2d\u6240\u6709\u91cd\u590d\u6570\u5b57\u7684\u8282\u70b9\uff0c\u53ea\u7559\u4e0b\u4e0d\u540c\u7684\u6570\u5b57 \u3002\u8fd4\u56de \u5df2\u6392\u5e8f\u7684\u94fe\u8868 \u3002\n<\/em>\n<\/em>\n<\/em>\n<\/em> \u793a\u4f8b 1\uff1a\n<\/em>\n<\/em>\n<\/em> \u8f93\u5165\uff1ahead = [1,2,3,3,4,4,5]\n<\/em> \u8f93\u51fa\uff1a[1,2,5]\n<\/em> \u793a\u4f8b 2\uff1a\n<\/em>\n<\/em>\n<\/em> \u8f93\u5165\uff1ahead = [1,1,1,2,3]\n<\/em> \u8f93\u51fa\uff1a[2,3]\n<\/em>\n<\/em>\n<\/em> \u63d0\u793a\uff1a\n<\/em>\n<\/em> \u94fe\u8868\u4e2d\u8282\u70b9\u6570\u76ee\u5728\u8303\u56f4 [0, 300] \u5185\n<\/em> -100 <= Node.val <= 100\n<\/em> \u9898\u76ee\u6570\u636e\u4fdd\u8bc1\u94fe\u8868\u5df2\u7ecf\u6309\u5347\u5e8f \u6392\u5217\n<\/em>\n<\/em> * <\/em>@author <\/em><\/strong>zeroheart\n<\/em> *\n<\/em> *\/\n<\/em>public class Question82 {\n\n    public static ListNode deleteDuplicates(ListNode head) {\n        \/\/ \u6211\u662f\u5728\u771f\u7684\u4e0d\u4f1a\u94fe\u8868\u3002\u3002\u3002\u3002\u6284\u4e00\u4e2a\u5148\u3002\u3002\u3002\n        \n        \/\/dummy\u8282\u70b9\n        ListNode dummy = new ListNode(0);\n        dummy.next = head;\n        \/\/\u8bb0\u5f55\u524d\u7f6e\u8282\u70b9\uff0c\u5904\u7406\u8981\u5220\u9664\u7684\u60c5\u51b5\n        ListNode pre = dummy;\n        \/\/\u8bb0\u5f55\u5f53\u524d\u8282\u70b9\uff0c\u9700\u8981\u904d\u5386\u6574\u4e2a\u94fe\u8868\n        ListNode cur = head;\n\n        while(cur != null){\n            \/\/\u627e\u5230\u4e0b\u4e00\u4e2acur\u548ccur.next\u4e0d\u76f8\u540c\u7684\u4f4d\u7f6e\n            while(cur.next != null && cur.val == cur.next.val){\n                cur = cur.next;\n            }\n            \/\/cur\u5f80\u524d\u8d70\u4e00\u6b65\uff0c\u4e3a\u4e0d\u76f8\u540c\u7684\u4e24\u4e2a\u503c\u7684\u540e\u8005\uff0c\u59823->3->4, \u4e0d\u76f8\u540c\u7684\u4f4d\u7f6e\u4e3a3->4,\u540e\u8005\u4e3a4\n            cur = cur.next;\n            \/**\n<\/em>             * \u5982\u679c\u524d\u7f6e\u8282\u70b9\u548ccur\u7684\u4f4d\u7f6e\u8d85\u8fc72\uff0c\u59821->2->3\uff0c3\u548c1\u7684\u8ddd\u79bb\u672a\u8d85\u8fc72\uff0c\u53cd\u4e4b1->2->2->3,3\u548c1\u7684\u8ddd\u79bb\u8d85\u8fc72\n<\/em>             * \u5219\u5c06\u524d\u7f6e\u8282\u70b9pre\u76f4\u63a5\u8fde\u63a5\u5f53\u524d\u8282\u70b9cur\n<\/em>             * \u5426\u5219\u524d\u7f6e\u8282\u70b9\u5411\u524d\n<\/em>             *\/\n<\/em>            <\/em>if(pre.next.next != cur){\n                pre.next = cur;\n            }else{\n                pre = pre.next;\n            }\n        }\n\n        return dummy.next;\n    }\n\n    public static void main(String[] args) {\n    }\n}<\/pre>\n\n\n\n
15. \u4e09\u6570\u4e4b\u548c<\/a><\/p>\n\n\n\n
\u8fd9\u9898\u4e5f\u662f\u4e8c\u5206\uff0c\u4e3b\u8981\u7684\u4f9d\u636e\u662f\u8981\u5148\u6392\u5e8f\uff0c\u5982\u679cnum[0]>0\u5c31\u76f4\u63a5\u8fd4\u56de\u4e86\uff0c\u5426\u5219\u904d\u5386\u6570\u7ec4\uff0c\u5f97\u5230nums[i]\uff0c\u5b9a\u4e49low\u548chigh\uff0c\u8fd9\u4e09\u4e2a\u6570\u4e4b\u540e\u4e3a0\u7684\u5c31\u662f\u8981\u7684\u6570\u636e\u3002\u6ce8\u610f\u91cd\u590d\u6570\u636e\u7684\u5904\u7406\u3002<\/p>\n\n\n\n

\/**
<\/em> *
<\/em>
<\/em> 15. \u4e09\u6570\u4e4b\u548c
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u5305\u542b n \u4e2a\u6574\u6570\u7684\u6570\u7ec4 nums\uff0c\u5224\u65ad nums \u4e2d\u662f\u5426\u5b58\u5728\u4e09\u4e2a\u5143\u7d20 a\uff0cb\uff0cc \uff0c\u4f7f\u5f97 a + b + c = 0 \uff1f\u8bf7\u4f60\u627e\u51fa\u6240\u6709\u548c\u4e3a 0 \u4e14\u4e0d\u91cd\u590d\u7684\u4e09\u5143\u7ec4\u3002
<\/em>
<\/em> \u6ce8\u610f\uff1a\u7b54\u6848\u4e2d\u4e0d\u53ef\u4ee5\u5305\u542b\u91cd\u590d\u7684\u4e09\u5143\u7ec4\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = [-1,0,1,2,-1,-4]
<\/em> \u8f93\u51fa\uff1a[[-1,-1,2],[-1,0,1]]
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = []
<\/em> \u8f93\u51fa\uff1a[]
<\/em> \u793a\u4f8b 3\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = [0]
<\/em> \u8f93\u51fa\uff1a[]
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 0 <= nums.length <= 3000
<\/em> -10^5 <= nums[i] <= 10^5
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question15 {
   public static List<List<Integer>> threeSum(int[] nums) {
      \/\/ \u8fd9\u9898\u89e3\u6cd5\u8fd8\u662f\u6709\u4e9b\u590d\u6742\u7684\uff0c\u770b\u4e86\u8bc4\u8bba\u533a\u7684\u601d\u8def\uff0c\u5199\u5199\u770b\uff0c\u53cc\u6307\u9488\u5904\u7406

      if(nums.length<3) return new ArrayList<>();

      List<List<Integer>> result = new ArrayList<>();
      Arrays.sort<\/em>(nums);

      \/\/ int low = 0;
      \/\/ int high = nums.length - 1;

      for(int i = 0; i < nums.length - 2; i++){
         \/\/ \u8fd9\u4e24\u4e2a\u9700\u8981\u653e\u5230for\u5faa\u73af\u91cc\u9762\uff0c\u5426\u8d3chigh\u4e0d\u66f4\u65b0\uff0c\u4f1a\u5c11\u6570\u636e
         int low = i + 1;
         int high = nums.length - 1;

         \/\/ \u91cd\u590d\u7684\uff0c\u53ef\u4ee5\u8df3\u8fc7
         if(i>0  && nums[i] == nums[i-1]) continue;

         while(low < high){
            int sum = nums[i] + nums[low] + nums[high];
            if(sum<0){
               low++;
            }else if(sum>0) {
               high--;
            }else {
               ArrayList<Integer> r = new ArrayList<>();
               r.add(nums[i]);
               r.add(nums[low]);
               r.add(nums[high]);
               result.add(r);

               while (low < high && nums[low] == nums[low+1]){
                  low++;
               }

               while (low < high && nums[high] == nums[high-1]){
                  high--;
               }

               low++;
               high--;

            }
         }
      }

      return result;

   }


   public static void main(String[] args) {
\/\/    System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
      System.out<\/em>.println(threeSum<\/em>(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));
   }
}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
82. \u5220\u9664\u6392\u5e8f\u94fe\u8868\u4e2d\u7684\u91cd\u590d\u5143\u7d20 II \u94fe\u8868\u76f8\u5173\u7684\u9898\u76ee\uff0c\u6211\u662f\u771f\u4e0d\u4f1a\u3002\u3002 \/** 82. \u5220\u9664\u6392\u5e8f\u94fe\u8868\u4e2d\u7684\u91cd\u590d\u5143 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[157],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2717"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2717"}],"version-history":[{"count":7,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2717\/revisions"}],"predecessor-version":[{"id":2724,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2717\/revisions\/2724"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2717"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2717"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2717"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}