Step1. 循环时,将 key= target-num[i] ,value = i 存入hashmap
Step2. 下一次循环时 若num[i+1] = value 则返回对应的下标
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (target == nums[i] + nums[j]) { return new int[]{i, j}; } } } return null; } }总结
1. leetcode 提交代码时 不需要import jdk包含的包。
2. 复习时间复杂度。这里的时间复杂度依然是 O(n²),若能找到更小的时间复杂度希望读者能够留言
3. 进阶 - 复习haspMap时间复杂度(不发生碰撞时,hashmap所有方法时间复杂度为O(1))
进阶// 这里haspmap不发生碰撞的话,该方法时间复杂度为O(n) // 思路 // Step 1 循环遍历 nums // Step 2 每次循环计算流程 // Step 2-1 判断 hash Map 中是否有nums[i] 有保存结果indexs ,return indexs // Step 2-2 put(target-nums[i],i) 到 hash Map中 class Solution { public int[] twoSum(int[] nums, int target) { int[] indexs = new int[2]; // 建立k-v ,一一对应的哈希表 HashMaphash = new HashMap (); for(int i = 0; i < nums.length; i++){ if(hash.containsKey(nums[i])){ indexs[0] = hash.get(nums[i]); indexs[1] = i; return indexs; } hash.put(target-nums[i],i); } return indexs; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)