数组查找算法，数组，a + b = c

题目

给定一个无序数组，例如int[] arr={3，5，8，9，12，21，27}，列出所有满足条件的集合：

1. 集合中包含两个值a、b(a和b都在数组中，且a不等于b)
2. a+b=c,c也要在数组中

思考

1. 先排序。
2. 用 a 和 b的索引来做嵌套循环，a主循环，b子循环，迭代出所有a+b的组合。
3. 将c的索引加入到子循环中，若
   arr[a] + arr[b] > arr[c] 则将c++,向右继续寻找有可能相等的c。
   arr[a] + arr[b] < arr[c] 则说明右边不可能有相等的c，直接b++，找下一个a+b。
   相等则放入数组中。

总结

主要思路是利用排序好的数组从小到大的原理，移动a和b，然后在b的右侧寻找相等的c.

Java解法

package learning;
import java.util.*;
public class ArraySearcher {
    public static List<int[]> searchABC(int[] arr) {
        if (null == arr || arr.length == 0) {
            return null;
        }

        int length = arr.length;
        List<int[]> abcPair = new ArrayList<>();
        //先从小到大排序
        Arrays.sort(arr);
        //主循环,用于a的起点向右移动
        for (int a = 0; a < length ; a++) {
            int b = a;
            int c = a + 1;
            //子循环，主要移动c来查找a+b=c
            while (c < length) {  //从左到右
                if (arr[a] + arr[b] > arr[c]) {  
//因为数组有序，所以若a + b > c 则说明c有可能在右边,移动c
                    c++;
                } else if (arr[a] + arr[b] < arr[c]) {  
//若 a + b < c,c不可能在右边，b往右移
                    b++;
                } else {
                    int[] pair = {arr[a],arr[b],arr[c]};  
//找到abc，加入列表
                    abcPair.add(pair);
                    c++;
                }
            }
        }
      return abcPair;
    }

    public static void main(String[] args) {
        int[] lst = {3,5,8,9,12,21,27};
        List<int[]>  result = ArraySearcher.searchABC(lst);
        for(int[] l: result) {
            System.out.println(l[0]+ " + " + l[1] + " = " + l[2]);
        }
    }

}