郓城网站制作,网站后台维护技能,崇州网站制作,中国建筑网站平台有哪些题目一#xff1a;两数之和
给出一个整型数组 numbers 和一个目标值 target#xff0c;请在数组中找出两个加起来等于目标值的数的下标#xff0c;返回的下标按升序排列。
#xff08;注#xff1a;返回的数组下标从1开始算起#xff0c;保证target一定可以由数组里面2…题目一两数之和
给出一个整型数组 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 hereint n numbers.length;int[] res {-1, -1};//遍历数组for (int i 0; i n; i) {for (int j i 1; j n; j) {//判断相加值是否为targetif (numbers[i] numbers[j] target) {res[0] i1;res[1] j1;//返回值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) {HashMapInteger, 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 hereint sum_min Integer.MAX_VALUE;int result0;for(int i0;inums.length-2;i){for(int ji1;jnums.length-1;j){for(int kj1;knums.length;k){int sumnums[i]nums[j]nums[k];if(Math.abs(sum-target)sum_min){sum_minMath.abs(sum-target);resultsum;}}}}return result;}
}
方法二先排序再循环
数组在没有排序之前不容易实现某种算法排序完之后在固定第一个数字的情况下通过与之后数据中头尾数据相加得sum与target求差循环比对差距大小。同时头尾数据会根据与target大小做调整当sumtarget时尾数据下标-1当sumtarget时头数据下标1sumtarget则可以直接返回。
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;}
}
