【Algorithm】数组：1题-两数之和 & 268题-缺失数字

1题两数字和

题目： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

暴力解题法：

思想：遍历每个元素和其他元素相加的和，结果为target则返回 #python3 ： class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: # 暴力解题法(n个元素) length = len(nums) # 将每一个元素与其后面的元素相加共需要n-1轮 for i in range(length - 1): # 每一轮需要相加的元素从i+1到n for j in range(i+1, length): if nums[i] + nums[j] == target: return i,j //java public class doubleSum { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; int length = nums.length; for(int i = 0; i < length-1; i++){ for(int j = i + 1; j < length; j++){ if(nums[i] + nums[j] == target){ result[0] = i; result[1] = j; } } } return result; } public static void main(String[] args) { int[] arr = {3,6,8,5,9}; int target = 8; doubleSum ds = new doubleSum(); System.out.println(Arrays.toString(ds.twoSum(arr,target))); } } //显示结果 [0, 3]

Map：

//思想：将每一个x计算(target-x)与Map中的每一个key对比是否相等，如果相等则返回该键值对， // 如果不相等则将x存入Map的Key中，x的下标存入Map的value中，直到找到结果，否则返回空 import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class doubleSum_1_1 { public int[] twoSum(int[] nums, int target){ Map<Integer,Integer> hashTable = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++){ //如果表中存在(target-x)和key相等,则返回其键值对 if (hashTable.containsKey(target - nums[i])){ return new int[]{hashTable.get(target - nums[i]), i}; } //不存在则将x和x的下标加入Map中 hashTable.put(nums[i], i); } return new int[0]; } public static void main(String[] args) { int[] arr = {3,6,8,5,9}; int target = 8; doubleSum_1_1 ds11 = new doubleSum_1_1(); System.out.println(Arrays.toString(ds11.twoSum(arr,target))); } }

---

268缺失数字

sort：

题目： 给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。如果序列为[0，1，2]则返回末尾加一。

public class missingNumber_268_0 { public int missingNumber(int[] nums){ Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (i != nums[i]) { return i; } } return nums.length; } public static void main(String[] args) { int[] arr = {3, 2, 0, 1}; missingNumber_268_0 mn = new missingNumber_268_0(); System.out.println(mn.missingNumber(arr)); } }

HashSet：

hashSet中的contains方法能够直接找出没有包含的元素

public class missingNumber_268_1 { public int missingNumber(int[] nums){ HashSet<Integer> hs = new HashSet<Integer>(); for (Integer h : nums) { hs.add(h); } for (int i = 0; i < nums.length; i++) { if (!hs.contains(i)) { return i; } } return nums.length; } public static void main(String[] args) { int[] arr = {3, 2, 0, 1, 5}; missingNumber_268_1 mn = new missingNumber_268_1(); System.out.println(mn.missingNumber(arr)); } }

最优解法 math (O(n)):

// 数学方法 0-n的数组加和为 n*(n+1)/2 减去 数组的sum就是缺失的数字 public class missingNumber_268_2 { public int missingNumber(int[] nums){ int len = nums.length; int sum = 0; for (int i = 0; i < nums.length; i++){ sum += nums[i]; } int number = len * (len + 1) / 2; return number - sum; } public static void main(String[] args) { int[] arr = {0, 1, 2, 4, 3}; missingNumber_268_2 m2 = new missingNumber_268_2(); System.out.println(m2.missingNumber(arr)); } }