【算法题】输入一维数组array和n，找出和值为n的任意两个元素

题目描述

输入一维数组array和n，找出和值为n的任意两个元素。例如：
array = [2, 3, 1, 10, 4, 30]
n = 31
则结果应该输出1, 30 顺序不重要。如果有多个满足条件的，返回任意一对即可。

源代码

双指针法。

package com.light.sword;

/**
 * @author: Jack
 * 2021/4/21 下午7:51
 * <p>
 * 输入一维数组array和n，找出和值为n的任意两个元素。例如：
 * array = [2, 3, 1, 10, 4, 30]
 * n = 31
 * 则结果应该输出1, 30 顺序不重要
 * 如果有多个满足条件的，返回任意一对即可
 */

public class ArraySumN {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 10, 4, 30};
        int[] ans = find(array, 31);
        System.out.println(ans[0]);
        System.out.println(ans[1]);
    }

    public static int[] find(int[] array, int n) {
        int[] ans = new int[2];
        // 排序
        sort(array);

        int i = 0, j = array.length - 1;
        while (i < j) {
            if (array[i] + array[j] == n) {
                ans[0] = array[i];
                ans[1] = array[j];
                break;
            } else if (array[i] + array[j] < n) {
                i++;
            } else {
                j--;
            }
        }

        return ans;
    }

    public static void sort(int[] array) {
        // array elements 0:array.length
        for (int i = 0; i < array.length; i++) {
            // loop round j
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

}

冒泡排序说明：

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

(2)比较第2和第3个数，将小数 放在前面，大数放在后面。

......

(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

(6)依次类推，每一趟比较次数减少依次