学步园

1. 数组中两个元素相加等于指定数的所有组合（仅用一次循环且不能创建新的数组或者集合）

思路：从数组的前后两端(i=0,j=array.lengths)分别利用指针（计数器）来扫描数组，如果满足相加等于目标则打印，否则当sum<array[i]+array[j]则i++，否则j--

// 快速寻找满足条件的两个
// 数组中两个数的和满足指定结果
public class Test
{
    static int[] arr =
    {
            1, 5, 9, 3, 4, 7, 6, 2, 8
    };
    static int maxIndex = arr.length - 1;// 索引最大值
    static int sum = 11;// 求两个数的和等于的值

    public static void main(String[] args)
    {
        find1(arr);
    }

    // 如果:sum<arr[i]+arr[j] i++;如果:sum>arr[i]+arr[j] j--
    static void find1(int[] arr)
    {
        Arrays.sort(arr);// 对数组排序
        for (int i = 0, j = maxIndex; i < j  
        {
            if (arr[i] + arr[j] == sum)
            {
                System.out.println(sum + " = " + arr[i] + " + " + arr[j]);
                i++;
            }
            else if (arr[i] + arr[j] < sum)
            {
                i++;
            }
            else
            {
                j--;
            }
        }
    }
}

补充：启用两个指针（计数器）算法思维也适用于“从数组（单链表）中找出倒数第k个元素”

public static void main(String[] args) {

        int[] array = { 1, 5, 2, 87, 45, 13, 90 };
        int i1 = 0;
        int k = 3;
        int i2 = 0;

        while (array.length > 0) {
            i1++;
            //第一个指针先计数且已经走到目标间隔
            if (i1 == k) {
                //第二个指针的初始计数
                i2++;
                // 第二个指针开始时，第一个指针继续往下走
                i1++;
            }
               //仅当第二个指针已经开始，才继续计数
if (i2 > 0) {
                i2++;
            }
            //当第一个指针到底时
            if (i1 == array.length - 1) {
                System.out.println(i1);
                System.out.println(i2);
                System.out.println("target: " + array[i2]);
                return;
            }
        }
    }

2. 指定范围内的完数查找

循环指定范围的数，找出此数的整除数 sum += i //i为整除数

    public static void findPerfectNum(int n) {
        String str = "";
        int sum = 0;
        //不需要进行查找所有小于等于此数的循环，因为若i循环到大于次数的一半的值时，必然不能整除，则可以直接排除，减少循环量。比如1000内的完数，到501必然不能被1000整除了。
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                str += i + " ";
                sum += i;
            }
        }
        if (sum == n) {
            System.out.println(n + " its factors are " + str);
        }
    }