尺取法：PIPI的目标Ⅲ

深藏阁楼爱情的钟 2023-10-06 21:58 12阅读 0赞

## 尺取法：PIPI的目标Ⅲ ##

#### 文章目录 ####

*  尺取法：PIPI的目标Ⅲ
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

首先对数组R进行排序，如果直接枚举a,b,c的话，时间复杂度为O(n^3)，肯定会超时，那么我们接下来考虑使用尺取法来解决此题。  
  我们只枚举a，然后令b=a+1，即b为a的下一位，c=n。枚举过程如下：  
  如果此时R\[a\]+R\[b\]+R\[c\]==0，那么满足要求，我们输出结果，然后令b++，c- -，之后继续进行和的判断。  
  如果此时R\[a\]+R\[b\]+R\[c\]<0，那么显然我们的值小了。由于我们枚举的是a，所以此时a不能动，那么只能动b或者c，而只有动b才能让它变大，所以让b++，之后继续进行和的判断。  
  如果此时R\[a\]+R\[b\]+R\[c\]>0，那么显然我们的值大了。a不能动，那么只能动b或者c，而只有动c才能让它变小，所以让c- -，之后继续进行和的判断。  
  当b在c之后或b和c重叠时，则我们已经枚举完了当前a的所有情况，则a移到下一位，继续进行枚举判断过程

题目要求我们输出不重复的答案，因此我们将< a, b, c >定义为三元组TriGroup，用一个HashSet来进行去重。需要注意的是，我们必须重写TriGroup的equals方法，因为我们这里的逻辑是当三元组中a,b,c的值对应相等，则认为两个TriGroup是同一个，而默认的equals方法是通过==判断实现的。hashCode方法也要重写，因为HashSet的add方法，调用的实际上是其内置的HashMap的put方法，该方法是要使用到键的hash值的，而计算hash值就是用的hashCode方法，因此我们重写hashCode方法，使其返回a,b,c共同决定的hash值

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[] array = new int[1005];
        static Set<TriGroup> set = new HashSet<>();
        public static void main(String[] args) {
        
            int a, b, c, n, i, aIndex, bIndex, cIndex;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                set.clear();
                n = scanner.nextInt();
                for (i = 0; i < n; i++) {
        
                    array[i] = scanner.nextInt();
                }
                Arrays.sort(array, 0, n);
                for (i = 0; i < n - 2; i++) {
        
                    aIndex = i;
                    bIndex = i + 1;
                    cIndex = n - 1;
                    a = array[aIndex];
                    b = array[bIndex];
                    c = array[cIndex];
                    while (bIndex < cIndex) {
        
                        if (a + b + c < 0) {
        
                            bIndex++;
                            b = array[bIndex];
                        }
                        if (a + b + c > 0) {
        
                            cIndex--;
                            c = array[cIndex];
                        }
                        if (a + b + c == 0 && cIndex > bIndex) {
        
                            TriGroup triGroup = new TriGroup(a, b, c);
                            if (!set.contains(triGroup)) {
        
                                set.add(triGroup);
                                System.out.println(a + " " + b + " " + c);
                            }
                            bIndex++;
                            b = array[bIndex];
                            cIndex--;
                            c = array[cIndex];
                        }
                    }
                }
            }
        }
    
    
    }
    
    class TriGroup {
        
        public int a;
        public int b;
        public int c;
    
        public TriGroup(int a, int b, int c) {
        
            this.a = a;
            this.b = b;
            this.c = c;
        }
    
        @Override
        public boolean equals(Object o) {
        
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            TriGroup triGroup = (TriGroup) o;
            return a == triGroup.a && b == triGroup.b && c == triGroup.c;
        }
    
        @Override
        public int hashCode() {
        
            return Objects.hash(a, b, c);
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f4c8f35b7aee424ba94f1dbb43fd0db4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3cf9f20ee2bc4b1d88eace4bda01dcd2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16