如何編寫兩數之和的算法代碼

這篇文章主要介紹“如何編寫兩數之和的算法代碼”，在日常操作中，相信很多人在如何編寫兩數之和的算法代碼問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何編寫兩數之和的算法代碼”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那 兩個 整數，并返回它們的數組下標。

示例：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

package com.lau.javabase;

import org.junit.Test;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 時間復雜度排序：
 * O(1)——常數時間
 * O(logN)——對數時間
 * O(N)——線性時間
 * O(N*N)——2次指數時間
 * O(N*N*N)——3次指數時間
 *
 *給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那 兩個 整數，并返回它們的數組下標。
 *
 * 你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
 *
 * 你可以按任意順序返回答案。
 *
 * 來源：力扣（LeetCode）
 * 鏈接：https://leetcode-cn.com/problems/two-sum
 *
 * 測試用例：
 * 輸入：nums = [2,7,11,15], target = 9
 * 輸出：[0,1]
 * 解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 *
 * 來源：力扣（LeetCode）
 * 鏈接：https://leetcode-cn.com/problems/two-sum
 * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
 *
 */
public class TwoSumTest {

    @Test
    public void test(){
        int[] array = {1,5,10,9,12};

        Instant start = Instant.now();
        System.out.println("---------1--------");
        int[]resArray = findTwoIntBySum(array, 17);
        Instant end  = Instant.now();
        long timeElapsed = Duration.between(start, end).toNanos(); // 單位為毫秒
        System.out.println("程序1耗時：" + timeElapsed);
        Arrays.stream(resArray).forEach(System.out :: println);

        start = Instant.now();
        System.out.println("---------2--------");
        int[]resArray2 = findTwoIntBySum2(array, 17);
        end  = Instant.now();
        timeElapsed = Duration.between(start, end).toNanos(); // 單位為毫秒
        System.out.println("程序2耗時：" + timeElapsed);
        Arrays.stream(resArray2).forEach(System.out :: println);

        start = Instant.now();
        System.out.println("---------3--------");
        int[]resArray3 = findTwoIntBySum3(array, 17);
        end  = Instant.now();
        timeElapsed = Duration.between(start, end).toNanos(); // 單位為毫秒
        System.out.println("程序3耗時：" + timeElapsed);
        Arrays.stream(resArray3).forEach(System.out :: println);

        start = Instant.now();
        System.out.println("---------4--------");
        int[]resArray4 = findTwoIntBySum4(array, 17);
        end  = Instant.now();
        timeElapsed = Duration.between(start, end).toNanos(); // 單位為毫秒
        System.out.println("程序4耗時：" + timeElapsed);
        Arrays.stream(resArray4).forEach(System.out :: println);
    }

    /**
     * @Description:解法一，兩層遍歷
     * @param array
     * @param target
     * @return
     */
    private int[] findTwoIntBySum(int[] array, int target){
        int[] resArray = null;

        for(int i = 0; i < array.length - 1; i++){
            for(int j = i + 1; j < array.length; j++){
                if(target == array[i] + array[j]){
                    resArray = new int[]{i, j};
                    return resArray;
                }
            }
        }

        return resArray;
    }

    /**
     * @Description:解法二，依托HashMap,將數組值作為K，索引作為V存入Map
     * @param array
     * @param target
     * @return
     */
    private int[] findTwoIntBySum2(int[] array, int target){
        int[] resArray = null;

        //建立HashMap,存儲<k,v> K存值，V存索引
        Map<Integer, Integer> midMap = new HashMap<>();
//        Arrays.stream(array).forEach(s -> );

        for(int i = 0; i < array.length; i++){
            midMap.put(array[i], i);
        }

        for(int i = 0; i < array.length; i++){
           if(Objects.nonNull(midMap.get(target - array[i]))){
               resArray = new int[]{i, midMap.get(target - array[i])};
               return resArray;
           }
        }

        return resArray;
    }

    /**
     * @Description:解法三，兩層遍歷（解法一的變種）
     * @param array
     * @param target
     * @return
     */
    private int[] findTwoIntBySum3(int[] array, int target){
        int[] resArray = null;

        for(int i = 0; i < array.length - 1; i++){
            for(int j = i + 1; j < array.length; j++){
                if(target - array[i] == array[j]){
                    resArray = new int[]{i, j};
                    return resArray;
                }
            }
        }

        return resArray;
    }

    /**
     * @Description:解法四，依托HashMap，一次遍歷即可完成
     * @param array
     * @param target
     * @return
     */
    private int[] findTwoIntBySum4(int[] array, int target){
        int[] resArray = null;

        //建立HashMap,存儲<k,v> K存值，V存索引
        Map<Integer, Integer> midMap = new HashMap<>();
//        Arrays.stream(array).forEach(s -> );

        for(int i = 0; i < array.length; i++){
            if(midMap.containsKey(target - array[i])){
                resArray = new int[]{midMap.get(target - array[i]), i};
                return resArray;
            }

            midMap.put(array[i], i);
        }

        return resArray;
    }
}

到此，關于“如何編寫兩數之和的算法代碼”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！