JAVA整数数组中，找出其中两个数相加的和,并且找两个目标值的下标

阳光穿透心脏的1/2处 2023-06-17 09:58 13阅读 0赞

package cn.datamasking.test.NumSum;
    
    import java.util.Arrays;
    import java.util.HashMap;
    public class Test {
        public static void main(String[] args) {
            /**
             * 查找字符串数组中是否包含指定的值
             */
            boolean resultStr = false;
            String[] arrStr = {"3", "2", "39", "6", "55", "13", "9"};
            String targetStr = "9";
            resultStr = Arrays.asList(arrStr).contains(targetStr);
            System.out.println(resultStr);
    
            /**
             * 整数数组中，找出其中两个数相加的和,并且找两个目标值的下标
             */
            int[] arrInt = {3, 2, 39, 6, 55, 13, 9};
            int targetInt = 9;
            int[] two3 = findTwoSum(arrInt, targetInt);
            for (int key : two3) {
                System.out.println(key);
            }
            /**
             * Arrays.binarySearch()方法只能用于有序数组！！！如果数组无序的话得到的结果就会很奇怪
             */
            long startTime = System.nanoTime();
            System.out.println(useArraysBinarySearch(arrStr,targetStr));
            long endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("useArraysBinarySearch:  " + duration / 1000000);
    
            /**
             * 使用循环判断
             */
            long startTime1 = System.nanoTime();
            System.out.println(useLoop(arrStr,targetStr));
            long endTime1 = System.nanoTime();
            long duration1 = endTime1 - startTime1;
            System.out.println("useLoop:  " + duration1 / 1000000);
    
        }
        /**
         * 整数数组中，找出其中两个数相加的和等于目标值的下标
         */
        public static int[] findTwoSum(int[] arrs, int target) {
            // 结果数组
            int[] result = {-1, -1};
            // 目标是数组下标，所以键值对为<数值,数值对应数组下标>，这里要说一下，哈希表的查找的时间复杂度是O(1)
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            // 1.扫描一遍数组，加入哈希表，时间复杂度是O(n)
            for (int i = 0; i < arrs.length; i++) {
                map.put(arrs[i], i);
            }
            // 2.第二次扫描，目标值-当前值，差值作为key，看看map里有木有，没有就下一个循环，直到数组扫描完毕或找到value,所以最坏情况的时间复杂度是O(n)
            for (int i = 0; i < arrs.length; i++) {
                // 得到第二个数的值
                int two = target - arrs[i];
                // 如果存在第二个数的数组下标&&结果的两个数不是同一个数的值
                if (map.containsKey(two) && target != 2 * two) {
                    result[0] = i;
                    result[1] = map.get(two);
                    // 返回找到的两个数的数组下标
                    return result;
                }
            }
            // 没有找到
            return result;
        }
    
        /**
         * 查找字符串数组中是否包含指定的值
         * *  时间复杂度劣于useLoop为：优
         */
        public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
            int a = Arrays.binarySearch(arr, targetValue);
            if (a > 0)
                return true;
            else
                return false;
        }
        /**
         * 查找字符串数组中是否包含指定的值
         *  时间复杂度为：优
         */
        public static boolean useLoop(String[] arr, String targetValue) {
            for(String s: arr){
                if(s.equals(targetValue))
                    return true;
            }
            return false;
        }
    }