算法思想一：有序哈希

解题思路：

分别计算牛妹和牛牛的得分，根据得分进行判断结果：

计算方式：

1、首先定义一个哈希表 set，用于存放所有可能的累加和，并保证累加和是有序的。
2、然后遍历整个数组，将可能的累加和放入哈希表中 set。
3、最后遍历 set，看其中是否包含不能得到的累加和，由于是有序排列的，所以第一个不能得到的累加和，即是所求的分数

代码展示：

Python版本 

class Solution:
    def Throwdice(self , n , m , a , b ):
        # write code here
        # 如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
        return 'Sad' if self.getscore(a,n) > self.getscore(b,n) else 'Happy'
    # 计算牛牛或牛妹的得分
    def getscore(self, nums, n):
        # 记录所有可能的求和，并保证这些值是有序的
        sets = []
        # 枚举所有可能的和
        for i in range(n):
            total = 0
            for j in range(n):
                total += nums[j]
                sets.append(total)
        cur = 1
        for num in sets:
            # 如果当前累加和存在，则cur自增
            if num == cur:
                cur += 1
            else:
                return cur
        return cur

JAVA版本 

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param b int整型一维数组 b
     * @return string字符串
     */
    public String Throwdice (int n, int m, int[] a, int[] b) {
        //如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
        return getScore(a,n)>getScore(b,n)?"Happy":"Sad";
    }
    //计算牛牛或牛妹的得分
    private int getScore(int[] nums,int n){
        //记录所有可能的求和，并保证这些值是有序的
        Set<Integer> myset=new TreeSet<>();
        //枚举出所有可能的累加和
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                set.add(sum);
            }
        }
        int cur=1;
        for(Integer num:set){
            //如果当前累加和存在，cur自增1
            if(num==cur){
                cur++;
            }
            //如果不存在，返回cur
            else{
                return cur;
            }
        }
        return cur;
    }
}

复杂度分析

时间复杂度：采用两层循环，内层循环里每次将累加和放入set，由于往set插入元素的时间复杂度为，（k是所有累加和的数目），总共插入了次，所以总的时间复杂度是。

空间复杂度：需要额外大小为k的set集合，所以空间复杂度为

算法思想二：排序+贪心

解题思路：

分别计算牛妹和牛牛的得分，根据得分进行判断结果：

计算方式：

1、首先对数组nums进行排序，保证累加和是从小到大递增的
2、然后遍历整个nums数组，之前所有累加和的取值范围在[1,sum]，新增之后，新增的范围在，要向包含从1开始的所有数字，那么必然要小于等于。所以，如果当前，那么与之间就缺了一个，即找到第一个不能得到的累加和。
图解：

代码展示： 

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param b int整型一维数组 b
     * @return string字符串
     */
    public String Throwdice (int n, int m, int[] a, int[] b) {
        // write code here
        int score1 = help(n, a);
        int score2 = help(n, b);
        if(score1 < score2)
            return "Sad";
        return "Happy";
    }
    // 计算得分
    public int help(int n, int[] a){
        // 排序
        Arrays.sort(a);
        int sum = 0;
        // 遍历排序的集合，直到查出 a[i] > sum + 1
        for(int i = 0; i < n; ++i){
            //如果当前a[i]>sum+1，那么[a[i],a[i]+sum]与[1,sum]之间就缺了一个sum+1
            if(a[i] > sum + 1){
                break;
            }
            sum += a[i];
        }
        return sum+1;
    }
}

复杂度分析

时间复杂度：只需遍历nums数组一次，时间复杂度，但是需要进行排序预处理，排序的时间复杂度是，所以最终的时间复杂度是
空间复杂度：仅使用常数空间