java面试算法汇总-数组

数组

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

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){if(map.containsKey(target-nums[i])){return new int[]{map.get(target-nums[i]),i};}map.put(nums[i],i);}throw new IllegalArgumentException("no proper answer");}
}

[程序二] 删除有序数组的重复项： 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成

一般这种原地修改数组的题多半都考虑用双指针为最优解

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length ==0) return 0;int p=0,q=1;while(q<nums.length){if(nums[q]!=nums[p]){nums[p+1] = nums[q];p++;}q++;}return p+1;}
}

[程序三] 移除元素：

标签：拷贝覆盖

主要思路是遍历数组 nums，每次取出的数字变量为 num，同时设置一个下标 ans
在遍历过程中如果出现数字与需要移除的值不相同时，则进行拷贝覆盖 nums[ans] = num，ans 自增 1
如果相同的时候，则跳过该数字不进行拷贝覆盖，最后 ans 即为新的数组长度
这种思路在移除元素较多时更适合使用，最极端的情况是全部元素都需要移除，遍历一遍结束即可
时间复杂度：O(n)，空间复杂度：O(1)

class Solution {public int removeElement(int[] nums, int val) {int start = 0;for(int num:nums){if(num!=val){nums[start] = num;start++;}}return start;}
}