使用双重for循环解决“两数之和”问题

题目：两数之和
描述：给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
注意：假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素，返回两数的下标值，以数组形式返回。
思路：所谓暴力算法，就是使用双重for循环依次遍历给定的数组，直到找出两个数满足条件：nums[i] + nums[j] == target。但是这个算法有个缺陷，就是时间复杂度太高。算法题主要考虑时间复杂度，我们要尽量想办法降低时间复杂度，而无需考虑空间复杂度，因为现在计算机内存基本是够用的。
时间复杂度：O(N的平方)
空间复杂度：O(1)

package od;

import java.util.Arrays;

/**
 * 两数之和
 * 给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
 * 假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
 * 返回两数的下标值，以数组形式返回。
 * 原文地址：https://www.codernav.com/2823.html
 * 更多算法详解：https://www.codernav.com
 */
public class Odtest22 {
    public static void main(String[] args) {
        int[] result = f(new int[]{1, 2, 3, 4, 5, 6}, 10);
        System.out.println(Arrays.toString(result));
    }

    private static int[] f(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

其实这种暴力算法也有优化的空间的。上面的代码中，里层的for循环，int j = 1可以替换成int j = i +1,因为如果j从1开始，有部分值会被重复遍历。比如下方的数组中，i=1,j=2与i=2,j=1就是重复计算，i=1,j=3与i=3,j=1也是重复计算。
数组：nums[1,2,3,4,5,6]
i=0,j=1 -> nums[i]=1,nums[j]=2
i=0,j=2 -> nums[i]=1,nums[j]=3
i=0,j=3 -> nums[i]=1,nums[j]=4
i=0,j=4 -> nums[i]=1,nums[j]=5
i=0,j=5 -> nums[i]=1,nums[j]=6

i=1,j=1 -> nums[i]=2,nums[j]=2
i=1,j=2 -> nums[i]=2,nums[j]=3
i=1,j=3 -> nums[i]=2,nums[j]=4
i=1,j=4 -> nums[i]=2,nums[j]=5
i=1,j=5 -> nums[i]=2,nums[j]=6

i=2,j=1 -> nums[i]=3,nums[j]=2
i=2,j=2 -> nums[i]=3,nums[j]=3
i=2,j=3 -> nums[i]=3,nums[j]=4
i=2,j=4 -> nums[i]=3,nums[j]=5
i=2,j=5 -> nums[i]=3,nums[j]=6

i=3,j=1 -> nums[i]=4,nums[j]=2
i=3,j=2 -> nums[i]=4,nums[j]=3
i=3,j=3 -> nums[i]=4,nums[j]=4
i=3,j=4 -> nums[i]=4,nums[j]=5
i=3,j=5 -> nums[i]=4,nums[j]=6

i=4,j=1 -> nums[i]=5,nums[j]=2
i=4,j=2 -> nums[i]=5,nums[j]=3
i=4,j=3 -> nums[i]=5,nums[j]=4
i=4,j=4 -> nums[i]=5,nums[j]=5
i=4,j=5 -> nums[i]=5,nums[j]=6

i=5,j=1 -> nums[i]=6,nums[j]=2
i=5,j=2 -> nums[i]=6,nums[j]=3
i=5,j=3 -> nums[i]=6,nums[j]=4
i=5,j=4 -> nums[i]=6,nums[j]=5
i=5,j=5 -> nums[i]=6,nums[j]=6