Google Onsite面经

请问k sum smaller使用递归吗？private static void helper(int[] arr, int target, int start, int k) ？

写了下k sum,欢迎指教

1. public class KSumSmaller {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {3, 1, 5, 2, 4};
   
5.                 int res = findKSumSmaller(arr, 9, 3);
   
6.                 System.out.println(res);
   
7.         }
   
8.        
   
9.         static int count = 0;
   
10.         public static int findKSumSmaller(int[] arr, int target, int k) {
    
11.                 if (arr == null || arr.length == 0) {
    
12.                         return 0;
    
13.                 }
    
14.                 Arrays.sort(arr);
    
15.                 if (k == 1) {
    
16.                         for (int i : arr) {
    
17.                                 if (i < target) {
    
18.                                         count += 1;
    
19.                                 }
    
20.                         }
    
21.                 }  else if (k == 2) {
    
22.                         findTwoSumSmaller(arr, target, 0);
    
23.                 } else {
    
24.                         helper(arr, target, 0, k);
    
25.                 }
    
26.                 return count;
    
27.         }
    
28.        
    
29.         public static void findTwoSumSmaller(int[] arr, int target, int start) {
    
30.                 if (arr == null || arr.length == 0) {
    
31.                         return;
    
32.                 }
    
33.                 Arrays.sort(arr);
    
34.                 int left = start;
    
35.                 int right = arr.length - 1;
    
36.                 while (left < right) {
    
37.                         int sum = arr[left] + arr[right];
    
38.                         if (sum < target) {
    
39.                                 count += right - left;
    
40.                                 left++;
    
41.                         } else {
    
42.                                 right--;
    
43.                         }
    
44.                 }
    
45.         }
    
46. 
    
47.         private static void helper(int[] arr, int target, int start, int k) {
    
48.                 if (start >= arr.length) {
    
49.                         return;
    
50.                 }
    
51.                 if (k == 2) {
    
52.                         findTwoSumSmaller(arr, target, start);
    
53.                 } else {
    
54.                         if (arr[start] < target) {
    
55.                                 helper(arr, target - arr[start], start + 1, k - 1);
    
56.                                 helper(arr, target, start + 1, k);
    
57.                         }
    
58.                 }
    
59.         }
    
60. }
    

复制代码