算法刷题之数组篇

题目一：两数之和

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

方法一，双层for遍历：

不过，这种方法在牛客网上执行的时候报超时错误

import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int n = numbers.length;
        int[] res = {-1, -1};
        //遍历数组
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                //判断相加值是否为target
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                    //返回值
                    return res;
                }
            }
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：O(n^2) 遍历两次数组
• 空间复杂度：O(1) 未申请额外空间

?方法二，hash表

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @param target int整型
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历数组
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                // 这里题目要求下标在数组中升序排列，这里这样放直接就满足了题意，因为数据A肯定先放入map，后面containsKey判断得出的数据B的下标i肯定大于数据A下标
                return new int[] {map.get(target - numbers[i]) + 1, i + 1};
            } else {
                map.put(numbers[i], i);
            }
        }
        throw new IllegalArgumentException("No solution");
    }
}

复杂度分析：

• 时间复杂度：O(n) 一次遍历hash索引查找时间复杂度为O(1)
• 空间复杂度：O(n) 申请了n大小的map空间

题目二：最接近的三数之和?

描述

给定一个数组 nums 和一个目标值 target ，请问从 nums 中选出三个数，使其之和尽量接近目标数，即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

数据范围：数组长度满足3≤n≤300??，数组中的值满足 ∣nums[i]∣≤1000??，目标值满足∣target∣≤10^4?，可以保证只有一个结果。

?方法一，暴力三层循环

循环累加，计算三个数之和与目标值target差值绝对值最小

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int ClosestSum (int[] nums, int target) {
        // write code here
        int sum_min = Integer.MAX_VALUE;
        int result=0;
        for(int i=0;i<nums.length-2;i++){
            for(int j=i+1;j<nums.length-1;j++){
                for(int k=j+1;k<nums.length;k++){
                   int sum=nums[i]+nums[j]+nums[k];
                    if(Math.abs(sum-target)<sum_min){
                        sum_min=Math.abs(sum-target);
                        result=sum;
                    }
                }
            }
        }
        return result;
    }
}

方法二，先排序再循环?

数组在没有排序之前不容易实现某种算法，排序完之后，在固定第一个数字的情况下，通过与之后数据中头尾数据相加得sum，与target求差，循环比对差距大小。同时头尾数据会根据与target大小做调整，当sum>target时，尾数据下标-1，当sum<target时，头数据下标+1，sum=target，则可以直接返回。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int ClosestSum (int[] nums, int target) {
        // write code here
        // 排序
        Arrays.sort(nums);
        // 记录结果
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            // 头尾数据下标
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                //每次头尾数据变更之后，比对差值大小
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
                if (sum > target) {
                    end--;
                } else if (sum < target) {
                    start++;
                } else {
                    return sum;
                }

            }

        }
        return res;

    }
}