算法问题——（双指针）

在这个特殊的假期里，由于牛牛在家特别无聊，于是他发明了一个小游戏，游戏规则为：将字符串数字中为偶数位的数字进行翻转，将翻转后的结果进行输出。

import java.util.*;


public class Solution {
    /**
     * 
     * @param number string字符串 
     * @return string字符串
     */
    public String change (String number) {
        if(number == null || number.length() == 0 || number.length() > Math.pow(10,7)){
            return number;
        }
        char[] temp = number.toCharArray();
        int left = 0;
        int right = temp.length - 1;

        while(left < right){
            if(temp[left]%2!=0){
                left++;
                continue;
            }
            if(temp[right]%2!=0){
                right--;
                continue;
            }
            
            char tempNum = temp[left];
            temp[left] = temp[right];
            temp[right] = tempNum;
            left++;
            right--;
        }
        return String.valueOf(temp);
    }
}

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

import java.util.ArrayList;
public class Solution {
    public ArrayList FindNumbersWithSum(int [] array,int sum) {
        ArrayList list = new ArrayList();
        //如果是最小的数据都是大于sum 那么就不存在
        if (array.length==0||array[0] > sum) {
            return list;
        }
        int left = 0;
        int right = array.length - 1;
        
        while (left  array[left] * array[right]) {
                        list.clear();
                        list.add(array[left]);
                        list.add(array[right]);
                    }
                }
                left++;
                right--;
            } else if (array[left] + array[right] > sum) {
                right--;
            } else {
                left++;
            }
        }
        return list;
    }
}

题目描述

给定一个无序数组arr，找到数组中未出现的最小正整数

例如arr = [-1, 2, 3, 4]。返回1

       arr = [1, 2, 3, 4]。返回5

[要求]

时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)

/**
 * Copyright (C), 2018-2020
 * FileName: Main001_double_pointer
 * Author:   xjl
 * Date:     2020/7/6 14:17
 * Description: 双指针
 */
package Double_pointer;

import java.util.Arrays;
import java.util.Scanner;
//这个方法不符要求 只能通过20%的用例测试
public class Main001_double_pointer {

    public static void main(String[] args) {
        //数据的输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] array = new int[m];
        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }
        //函数的调用
        int result = test(array);
        //结果的显示
        System.out.println(result);
    }

    public static int test(int[] array) {
        int res=1;
        Arrays.stream(array);
        for (int i = 0; i < array.length; i++) {
            if (res!= array[i]) {
                return res;
            }
            res++;
        }
        return array[array.length - 1] + 1;
    }
}

import java.util.*;

public class Main{
   public static void main(String[] args){
        //数据的输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] array = new int[m];
        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }
        //函数的调用
        int result = test(array);
        //结果的显示
        System.out.println(result);
    }
    
     public static int test(int[] array) {
        ArrayList list = new ArrayList();
        for (int i=0;i 0 && nums[i] == nums[i - 1]) continue;
            //制定两个指针
            int L = i + 1;
            int R = len - 1;
            //如果是左边的指针小于就表示可以进行
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    //添加进入list中
                    result.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    // 左边去重
                    while (L < R && nums[L] == nums[L + 1]) L++;
                    // 右边去重
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    L++;
                    R--;
                } else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return result;
    }
}

18. 四数之和

class Solution {
    public List fourSum(int[] nums, int target) {
        //除重复
        Set set = new HashSet();
        List result = new ArrayList();
        Arrays.sort(nums);//排序
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int p = j + 1;
                int q = nums.length - 1;
                int currentTarget = target - nums[i] - nums[j];
                while (p < q) {
                    int sum = nums[p] + nums[q];
                    if (sum == currentTarget) {
                        List list = new ArrayList();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[p]);
                        list.add(nums[q]);
                        set.add(list);
                        p++;
                        q--;
                    } else if (sum < currentTarget) {
                        p++;
                    } else {
                        q--;
                    }
                }
            }
        }
        for (List list : set) {
            result.add(list);
        }
        return result;
    }
}

923. 三数之和的多种可能

class Solution {
    public int threeSumMulti(int[] A, int target) {
         int MOD = 1_000_000_007;
        long ans = 0;
        Arrays.sort(A);
        for (int i = 0; i < A.length; ++i) {
            int T = target - A[i];
            int j = i + 1, k = A.length - 1;
            while (j < k) {
                if (A[j] + A[k] < T)
                    j++;
                else if (A[j] + A[k] > T)
                    k--;
                else if (A[j] != A[k]) {
                    int left = 1, right = 1;
                    while (j + 1 < k && A[j] == A[j + 1]) {
                        left++;
                        j++;
                    }
                    while (k - 1 > j && A[k] == A[k - 1]) {
                        right++;
                        k--;
                    }
                    ans += left * right;
                    ans %= MOD;
                    j++;
                    k--;
                } else {
                    ans += (k - j + 1) * (k - j) / 2;
                    ans %= MOD;
                    break;
                }
            }
        }
        return (int) ans;
    }
}