2024春招冲刺题单 ONT68 最接近的三数之和【中等 数组，递归 Java,Go,PHP】

题目

题目链接：
https://www.nowcoder.com/practice/f889497fd1134af5af9de60b4d13af23
相同题目:
https://www.lintcode.com/problem/59

思路

	本题答案是n数之和相关问题的模板。
1

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int ClosestSum (int[] nums, int target) {
        int[] help = {0, -1}; //-1表示help还没有赋值
        dfs(nums, 0, new ArrayList<>(), 0, target, help);
        return help[0];
    }

    //N数之和的递归模版
    public void dfs(int[] nums, int index, List<Integer> path, int sum, int target,
                    int[] help) {
        if (path.size() == 3) {
            int diff = Math.abs(sum - target);
            if (help[1] == -1) {
                help[0] = sum;
                help[1] = diff;
            } else if (help[1] > diff) {
                help[0] = sum;
                help[1] = diff;
            }
            return;
        }

        for (int i = index; i < nums.length ; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1, path, sum + nums[i], target, help);
            path.remove(path.size() - 1); //恢复现场
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

参考答案Go

package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param target int整型
 * @return int整型
 */
func ClosestSum(nums []int, target int) int {
	help := []int{0, -1} //-1 表示还没有赋值
	path := []int{}
	dfs(nums, 0, path, 0, target, &help)
	return help[0]
}

//n数之和的递归模版
func dfs(nums []int, index int, path []int, sum int, target int, help *[]int) {
	if len(path) == 3 {
		diff := sum - target
		if diff < 0 {
			diff = diff * -1 //绝对值
		}

		if (*help)[1] == -1 {
			(*help)[0] = sum
			(*help)[1] = diff
		} else if (*help)[1] > diff {
			(*help)[0] = sum
			(*help)[1] = diff
		}

		return
	}

	for i := index; i < len(nums); i++ {
		path = append(path, nums[i])
		dfs(nums, i+1, path, sum+nums[i], target, help)

		path = path[:len(path)-1] //恢复现场
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
 */
function ClosestSum( $nums ,  $target )
{
   $help = [0,-1]; //-1表示还没有赋值
    dfs($nums,0,array(),0,$target,$help);
    return $help[0];
}


//n数之和的递归模板
function dfs($nums,$index,$path,$sum,$target,&$help){
    if(count($path) ==3) {
        $diff = $sum-$target;
        if($diff <0)
            $diff =$diff*-1;

        if($help[1] ==-1){
            $help[0] =$sum;
            $help[1] = $diff;
        }else if($help[1] > $diff){
            $help[0] =$sum;
            $help[1] = $diff;
        }
        return;
    }

    for($i=$index;$i<count($nums);$i++){
        array_push($path,$nums[$i]);
        dfs($nums,$i+1,$path,$sum+$nums[$i],$target,$help);
        array_pop($path);//恢复现场
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42