- 主题：数组
- （1）1. 两数之和
- （2）4. 寻找两个正序数组的中位数（错1）
- （3）11. 盛最多水的容器（错1）
- （4）15. 三数之和（错1）
- （5）16. 最接近的三数之和
- （6）18. 四数之和
- （7）26. 删除有序数组中的重复项
- （8）27. 移除元素
- （9）31. 下一个排列（错1）
- （10）33. 搜索旋转排序数组
法一：遍历
法二：利用哈希表存储剩余值和索引；
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap hashmap = new HashMap();
for(int i = 0; i < nums.length; i++){
if(hashmap.containsKey(nums[i])){
return new int[]{i, hashmap.get(nums[i])};
}
hashmap.put(target-nums[i],i);
}
return null;
}
}
（2）4. 寻找两个正序数组的中位数（错1）
（3）11. 盛最多水的容器（错1）
题解：双指针
class Solution {
public int maxArea(int[] height) {
int max = 0;
int area = 0;
int i = 0;
int j = height.length-1;
while(i < j){
if(height[i] < height[j]){
area = (j-i) * height[i];
}else{
area = (j-i) * height[j];
}
if(area > max){
max = area;
}
if(height[i] < height[j]){
i++;
}else{
j--;
}
}
return max;
}
}
（4）15. 三数之和（错1）
题解思路：排序+双指针：先对数组进行排序，每层遍历的索引比前面的大，避免部分重复搜索；当当前搜索的数值与前一轮搜索的数值一样时，跳过当前前轮，进入下一轮搜索；当第一轮数值确定时，后面两个之和就确定了，对后面两个数字使用双指针分别从数组前后开始搜索。
class Solution {
public List> threeSum(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
List> res = new ArrayList>();
for(int first = 0; first < len;first++){
if(first > 0 && nums[first] == nums[first - 1]){
continue;
}
int third = len - 1;
int target = - nums[first];
for(int second = first + 1; second < len; second++){
if(second > first + 1 && nums[second] == nums[second - 1]){
continue;
}
while(second < third && nums[second] + nums[third] > target){
third--;
}
if(second == third){
break;
}
if(nums[second] + nums[third] == target){
List list = new ArrayList();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
res.add(list);
}
}
}
return res;
}
}
（5）16. 最接近的三数之和
我的思路：与三数之和的方法一样，排序+双指针。
注意返回值的要求。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int close = Math.abs(nums[0] + nums[1] + nums[2] - target);
int res = nums[0] + nums[1] + nums[2];
int len = nums.length;
int temp;
Arrays.sort(nums);
List> list = new ArrayList>();
for(int first = 0; first < len;first++){
if(first > 0 && nums[first] == nums[first-1]){
continue;
}
for(int second = first+1; second < len;second++){
int third = len-1;
if(second > first+1 && nums[second] == nums[second-1]){
continue;
}
while(third > second){
temp = Math.abs(nums[first] + nums[second] + nums[third] - target);
if(temp < close){
close = temp;
res = nums[first] + nums[second] + nums[third];
}
third--;
}
}
}
return res;
}
}
（6）18. 四数之和
我的思路：在三数之和的基础上，加一层循环
class Solution {
public List> fourSum(int[] nums, int target) {
List> res = new ArrayList>();
int len = nums.length;
if(len < 4){
return res;
}
Arrays.sort(nums);
for(int first = 0; first < len; first++){
if(first > 0 && nums[first] == nums[first-1]){
continue;
}
for(int second = first + 1; second < len; second++){
if(second > first + 1 && nums[second] == nums[second-1]){
continue;
}
int fourth = len - 1;
int aim = target - nums[first] - nums[second];
for(int third = second+ 1; third < len; third++){
if(third > second+1 && nums[third] == nums[third-1]){
continue;
}
while(third < fourth && nums[third] + nums[fourth] > aim){
fourth--;
}
if(third == fourth){
break;
}
if(nums[third] + nums[fourth] == aim){
List list = new ArrayList();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
list.add(nums[fourth]);
res.add(list);
}
}
}
}
return res;
}
}
（7）26. 删除有序数组中的重复项
我的思路：每找到一个重复项，调整后面的所有数据项再检查后面的数据。
class Solution {
public int removeDuplicates(int[] nums) {
int len = nums.length;
if(len < 2){
return len;
}
int pre = 0;
int cur = 1;
while(cur < len){
int count = 0;
while(cur < len && nums[pre] == nums[cur]){
cur++;
count++;
}
for(int i = 1; cur-1+i < len; i++){
nums[pre+i] = nums[cur-1+i];
}
len -= count;
pre++;
cur = pre + 1;
}
return len;
}
}
题解：双指针法，在搜索的同时调整后面数据的位置，pre表示当前搜索完的位置，cur表示正在搜索检查的位置。不是检查一个调整一次，大大减小了时间复杂度。
class Solution {
public int removeDuplicates(int[] nums) {
int len = nums.length;
if(len < 2){
return len;
}
int pre = 0;
int cur = 1;
while(cur < len){
if(nums[pre] == nums[cur]){
cur++;
}else{
pre++;
nums[pre] = nums[cur];
cur++;
}
}
return pre+1;
}
}
（8）27. 移除元素
我的思路：双指针法，pre为当前检查完毕的位置，cur为正在检查的位置，在检查的过程中，同时调整数组。
class Solution {
public int removeElement(int[] nums, int val) {
if(nums.length == 0){
return 0;
}
int pre = 0;
int cur = 0;
while(cur < nums.length){
if(nums[cur] == val){
cur++;
}else{
nums[pre] = nums[cur];
pre++;
cur++;
}
}
return pre;
}
}
题解其他思路：双指针优化，因为题目说元素的位置可以变化，从左右两边开始检查，if left = val，将right复制到left，right–，直到left != val，left++，当right=left时，检查完成。
注意：right从length处开始，检查位置为right-1，可以保证元素只有一个时，也能进入循环。
class Solution {
public int removeElement(int[] nums, int val) {
if(nums.length == 0){
return 0;
}
int left = 0;
int right = nums.length;
while(left < right){
if(nums[left] == val){
nums[left] = nums[right-1];
right--;
}else{
left++;
}
}
return left;
}
}
（9）31. 下一个排列（错1）
题解思路：两遍扫描；从后往前找到
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
（10）33. 搜索旋转排序数组
我的思路：先找到旋转位置，判断target在哪半边数组，再进行二分查找，
class Solution {
public int search(int[] nums, int target) {
if(nums == null){
return -1;
}
if(nums.length == 1){
if(nums[0] == target){
return 0;
}else{
return -1;
}
}
int pre = 0;
int cur = 1;
while(cur < nums.length && nums[pre] < nums[cur]){
pre++;
cur++;
}
if(target >= nums[0]){
return binarySearch(nums,0,pre,target);
}else{
return binarySearch(nums,cur,nums.length-1,target);
}
}
public static int binarySearch(int[] nums, int left,int right, int target){
if(left <= right){
int mid = (left + right) / 2;
if(nums[mid] < target){
return binarySearch(nums,mid+1,right,target);
}else if(nums[mid] > target){
return binarySearch(nums,left,mid-1,target);
}else{
return mid;
}
}
return -1;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）