# 无序

说明:给定一个数组整数 number,从数组(这个数组要么没有解,要么只有唯一解)中找出两个数字满足相加之和与 number 相等,返回这两个数的下标值,以数组的形式返回,没有则返回 - 1

思路:可以利用 Map 集合将数组以 数值:下标 的形式存入 Map,然后令一个数字 i 等于目标值减去这个存入 Map 的数值,查看 Map 里面有没有这个数字 i 的存在,如果有则返回数字 i 的下标和 Map 的那个数字的 value

static int[] solution(int[] nums,int target){
        // 定义 Map 的内容类型,不然如果不定义的话下面的就需要强行转换成 int 的类型
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0; i < nums.length ; i++ ){
            // 判断 map 里面是否已经有了这个数字的存在
            if (map.containsKey(target-nums[i])){
                // 如果存在就返回这个这两个数字的下标形成的数组
                return new int[]{map.get(target-nums[i]),i};
            }
            // 将数组的数值和下标存入 map 中
            map.put(nums[i],i);
        }
        return new int[]{-1};
    }
// 主方法
   public static void main(String[] args) {
        int[] a ={1,2,6,9,12,10};
        int[] temp = solution(a, 10);
        for (int i = 0 ; i< temp.length ; i++){
            System.out.print(temp[i]+"    ");
        }
    }
// 控制台输出
// 0   3

# 有序(升序)

说明:这个数组是有序的,并且是升序排列的,其他条件和要求和无序的那个一样

思路:既然这个数组是有序的,那就要充分利用它的有序性,可以使用二分搜索算法、也可以使用双指针算法

# 使用二分搜索法找

具体:因为它有序了并且是要求要找到两个数字,所以就可以考虑使用二分法,以一个值为固定,其数组中寻找另一个数字,查找算法中二分法是比较好的。

static int[] FindOrderlyIndex(int[] nums, int target) {
        // 查找整个数组
        for (int i = 0; i < nums.length; i++) {
            // 记录数组的开始和结束的地方
            int low = i, high = nums.length - 1;
            // 二分搜索法出循环出口常规条件
            while (low <= high) {
                // 记录中间下标
                int mid = (high + low) / 2 ;
                // 如果相等就返回两个下标形成的数组
                if (target - nums[i] == nums[mid]) {
                    return new int[]{i, mid};
                } else if (target - nums[i] > nums[mid]) {
                    low = mid + 1;
                } else
                    high = mid - 1;
            }
        }
        return new int[]{-1};
    }
// 主方法
public static void main(String[] args) {
        int[] a = {1, 2, 6, 9, 10, 12};
        int[] temp = FindOrderlyIndex(a, 10);
        for (int i = 0; i < temp.length; i++) {
            System.out.print(temp[i] + "    ");
        }
    }
// 控制台输出:
// 0   3
// 如果将 target=10 改成 100,那么控制台就会输出
// -1

# 使用双指针

具体:充分利用有序的特性,将两个指针分别指向数组的头和尾部,如果两个数字之和大于目标值,那么就将右边的指针减一,反之则将左边的指针加一,当两个指针指向同一个目标的时候,那么在这个数组里面就是没有两个数字的和是目标值,则返回 - 1

static int[] DoublePointer(int[] nums, int target) {
    // 定义两个指针的开始部位
    int left = 0, right = nums.length - 1;
    // 如果两个指针相遇,那么就是没有找到两个数字,则返回 - 1
    while (left < right) {
        // 如果两个数字之和与目标值相等,那么就返回两个指针
        if (nums[left] + nums[right] == target) {
            return new int[]{left, right};
        } else if (nums[left] + nums[right] > target) {// 如果两数之和大于目标值,说明右边的值太大了
            right--;
        } else // 反之则说明左边的值太小了
            left++;
    }
    return new int[]{-1};
}
// 主方法
 public static void main(String[] args) {
        int[] a = {1, 2, 6, 9, 10, 12};
        int[] temp = DoublePointer(a, 10);
        for (int i = 0; i < temp.length; i++) {
            System.out.print(temp[i] + "    ");
        }
    }
// 控制台输出:
// 0   3
// 如果将 target=10 改成 100,那么控制台就会输出
// -1

还有暴力解法,就是使用两个 for 循环嵌套的去寻找

对比复杂度对使用

暴力解法:时间复杂度 O (n*n),空间复杂度 O (1)

MapHash:时间复杂度 O (n),空间复杂度 O (n)

二分法:时间复杂度 O (n*logn),空间复杂度 O (1)

双指针:时间复杂度 O (n),空间复杂度 O (1)

有待更新…