LeetCode每日三题（五）双指针

一、移动零

自己答案：

class Solution {
    public void moveZeroes(int[] nums) {
        for(int i=0;i<nums.length;i++){
            //定义一个计数器
            int count=0;
            //如果遍历到一个零元素
            if(nums[i]==0){
                //遍历零元素后面的元素
                for(int j=i;j<nums.length;j++){
                    //发现非零元素，交换顺序并且结束遍历
                    if(nums[j]!=0){
                        nums[i]=nums[j];
                        nums[j]=0;
                        break;
                    }else//没有发现则计数器加一
                        count++;
                }
            }else if(count==nums.length-i-1){
                //如果计数器为数组长度-当前索引值-1，则说明后面没有非零元素
                break;
            }
        }
    }
}

标准答案：

class Solution {
    public void moveZeroes(int[] nums) {
               int n = nums.length, left = 0, right = 0;
        while (right < n) {
            //若right指针是非零元素
            if (nums[right] != 0) {
                if(right==left){
                    //两个指针指向同一个位置
                    //直接跳过
                    right++;
                    left++;
                    continue;
                }else{
                    //交换元素
                    nums[left]=nums[right];
                    nums[right]=0;
                    //left指针+1
                    left++;
                }
            }
            //若right指针是零元素，则+1
            right++;
        }
    }
}

二、盛最多水的容器

自己答案：

class Solution {
    public int maxArea(int[] height) {
        int right=height.length-1;
        int left=0;
        int result=0;
        while(right!=left){
            int area=min(height[right],height[left])*(right-left);
            if(result<area){
                result=area;
            }
            if(height[right]<height[left]){
                right--;
            }else{
                left++;
            }
        }
        return result;
    }
        public  int min(int i,int j){
        if(j>i){
            return i;
        }else{
            return j;
        }
    }
}

标准答案： 

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
}

三、三数之和

自己答案：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
  //给整数数组排序
        Arrays.sort(nums);
        Set<List<Integer>> set=new HashSet<>();
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                int value=-nums[j]-nums[i];
                int index = Arrays.binarySearch(nums, j + 1, nums.length, value);
                if(index>=0){
                    //存在
                    List<Integer> temp=new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(nums[index]);
                    Collections.sort(temp);
                    set.add(temp);
                }
            }
        }
        for (List<Integer> integers : set) {
            List<Integer> list=new ArrayList<>();
            for (Integer integer : integers) {
                list.add(integer);
            }
            result.add(list);
        }
        return result;
    }
}

标准答案： 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // 双指针，目标是找到 nums[l] + nums[r] = -nums[i]
            int l = i + 1, r = nums.length - 1;
            int target = -nums[i];
             while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    // 跳过重复元素
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
}