package com.oracle.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.List;

import org.testng.annotations.Test;

public class TwoSumTest {
    //O(n) 利用哈希表，空间换时间
    public int[] twoSum(int sum, int [] arr) {
        int [] retIndex = new int[2];
        Map<Integer,Integer> m = new HashMap<Integer,Integer>();
        for(int i = 0;i<arr.length;i++) {
            m.put(arr[i], i);
        }

        for(int i=0;i<arr.length;i++) {
            int left = sum-arr[i];
            if(m.containsKey(left) && m.get(left)!=i) {
                retIndex[0] = i;
                retIndex[1] = m.get(left);
                break;
            }
        }

        return retIndex;
    } 

    //O(n方) 暴力解法
    public int [] twoSum1(int sum, int [] arr) {
        int [] ret = new int[2];
        for(int i=0;i<arr.length;i++) {
            for(int j=i+1;j<arr.length;j++) {
                if(arr[i]+arr[j] == sum) {
                    ret[0] = i;
                    ret[1] = j;
                    break;
                }
            }
        }
        return ret;
    }

    // O(n*log(n))  先排序，再二分，排序算法最好的时间复杂度是O(n*log(n))
    public int [] twoSum2(int sum, int [] arr) {
        int [] cloneArr = arr.clone();

        Arrays.sort(arr);

        int left = 0;
        int right = arr.length - 1;

        int [] values = new int[2];
        while(left < right) {
            if(arr[left] + arr[right]<sum) {
                left++;
            }else if(arr[left] + arr[right]>sum) {
                right--;
            }else {
                values[0] = arr[left];
                values[1] = arr[right];
                break;
            }
        }

        List<Integer> ret = new ArrayList<Integer>();
        for(int i = 0;i<cloneArr.length;i++) {
            if(values[0]== cloneArr[i]) {
                ret.add(i);
            }else if(values[1] == cloneArr[i]) {
                ret.add(i);
            }
        }

        return ret.stream().mapToInt(i->i).toArray();
        
    }


    @Test
    void testTwoSum() {
        int [] arr = {4, 4, 11, 15};
        int [] ret = twoSum2(8, arr);
        for(int i : ret) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

image.png