【14天算法入门】-第3天-双指针

末蓝、 2022-09-12 10:56 166阅读 0赞

**目录**

1、移动零

2、两数之和II——输入有序数组

--------------------

# 1、移动零 #

/**
     * 283. 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * */

**方法一：使用堆栈存储非0部分**

public void moveZeroes0(int[] nums) {
            //方法一:使用堆栈
            Stack<Integer> stack = new Stack<>();
            for(int i=0;i<nums.length;i++){
                if(nums[i] != 0){
                    stack.push(nums[i]);
                }
            }
            int zeroNum = nums.length - stack.size();
            for(int i=nums.length-1;i>=(nums.length - zeroNum);i--){
                nums[i] = 0;
            }
            for(int i=nums.length-zeroNum-1;i>=0;i--){
                nums[i] = stack.pop();
            }
        }

**方法二：不增加存储空间堆栈，直接保存非0值，后面补0**

public void moveZeroes(int[] nums) {
            //方法二：不增加存储空间堆栈，直接保存非0值，后面补0
            //2次遍历
            int i = 0;
            int inew = 0;
            while(i<nums.length){
                if(nums[i] != 0){
                    nums[inew++] = nums[i];
                }
                i++;
            }
    
            while(inew<nums.length){
                nums[inew++] = 0;
            }
        }

**方法三：双指针，分别指向已处理序列头部、未处理序列头部**

public void moveZeroes(int[] nums){
            //方法三：双指针
            //左指针指向已处理的序列尾部，右指针指向未处理的序列头部
            int left = 0;
            int right = 0;
    
            while(right<nums.length){
                if(nums[right] !=0){
                    if(nums[left] == 0){
                        swap(nums, left, right);
                        left++;
                    }else{
                        left++;
                    }
                }
                right++;
            }
        }
    
        public void swap(int[] nums, int left, int right){
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

# 2、两数之和II——输入有序数组 #

见【高效制胜】-day1 第二道题

[https://blog.csdn.net/weixin\_41770169/article/details/120455277?spm=1001.2014.3001.5501][https_blog.csdn.net_weixin_41770169_article_details_120455277_spm_1001.2014.3001.5501]

[https_blog.csdn.net_weixin_41770169_article_details_120455277_spm_1001.2014.3001.5501]: https://blog.csdn.net/weixin_41770169/article/details/120455277?spm=1001.2014.3001.5501